hdu(1754)——I hate it(更新节点,区间最值)
发布日期:2021-09-19 06:09:13
浏览次数:16
分类:技术文章
本文共 1625 字,大约阅读时间需要 5 分钟。
当C为'Q'的时候,表示这是一条询问操作,它询问ID从A到B(包括A,B)的学生当中,成绩最高的是多少。当C为'U'的时候,表示这是一条更新操作,要求把ID为A的学生的成绩更改为B。
题目大意就是这样,然后这道题呢,就是一道线段树的区间查询与端点更新的问题。
与区间和有所不同的是:这道题我们是维护线段树的最大值,所以在建树的时候,pushup时,我们要对父节点维护的是两个子节点中的最大值。
然后最后再注意一下更新的时候别忘记了要pushup来更新父节点。
#include#include #include #include using namespace std;#define maxn 222222int a[maxn];int ans=0;struct node{ int l,r; int val;}tree[maxn*4];void pushup(int v){ int temp=v*2; tree[v].val=max(tree[temp].val,tree[temp+1].val);}void build(int l,int r,int v){ tree[v].l=l; tree[v].r=r; tree[v].val=0; if(l==r){ tree[v].val=a[l]; return; } int mid=(l+r)/2; int temp=v*2; build(l,mid,temp); build(mid+1,r,temp+1); pushup(v);}void query(int l,int r,int v){ if(tree[v].l==l&&tree[v].r==r){ ans=max(ans,tree[v].val); return; } int mid=(tree[v].l+tree[v].r)>>1; int temp=v<<1; if(r<=mid) query(l,r,temp); else if(mid >1; if(pos<=mid) update(temp,pos,score); else if(pos>mid) update(temp+1,pos,score); pushup(v);}int main(){ int n,m; while(~scanf("%d%d",&n,&m)){ memset(a,0,sizeof(a)); for(int i=1;i<=n;i++) scanf("%d",&a[i]); build(1,n,1); char ss[6]; while(m--){ int aa,bb; scanf("%s",ss); if(ss[0]=='Q'){ ans=0; scanf("%d%d",&aa,&bb); query(aa,bb,0); printf("%d\n",ans); } else if(ss[0]=='U'){ scanf("%d%d",&aa,&bb); update(0,aa,bb); } } }}
转载地址:https://blog.csdn.net/ACMer_hades/article/details/46489341 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
不错!
[***.144.177.141]2024年04月11日 13时50分51秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
unity5.x assetbundle打包和加载
2019-04-27
C#用正则表达式去匹配被双引号包起来的中文
2019-04-27
lua table排序
2019-04-27
Unity发布的ios包在iphone上声音是从听筒里出来的问题
2019-04-27
UIScrollView复用节点示例
2019-04-27
Unity 5 AudioMixer
2019-04-27
Unity 代码混淆: CodeGuard的使用
2019-04-27
UGUI 列表循环使用
2019-04-27
使用命令行运行unity并执行某个静态函数(运用于命令行打包和批量打包)
2019-04-27
web.py框架
2019-04-27
web.py学习笔记
2019-04-27
python的代码缩进
2019-04-27
A* Pathfinding Project (Unity A*寻路插件) 使用教程
2019-04-27
bash学习笔记
2019-04-27
sqlite学习
2019-04-27
手把手教你实现Unity与Android的交互
2019-04-27
手把手教你使用Unity的Behavior Designer
2019-04-27
Unity3D摄像机裁剪——NGUI篇
2019-04-27
lua深拷贝一个table
2019-04-27
app运行提示Unable to Initialize Unity Engine
2019-04-27