hdu(1754)——I hate it(更新节点,区间最值)
发布日期:2021-09-19 06:09:13 浏览次数:1 分类:技术文章
当C为'Q'的时候,表示这是一条询问操作,它询问ID从A到B(包括A,B)的学生当中,成绩最高的是多少。

当C为'U'的时候,表示这是一条更新操作,要求把ID为A的学生的成绩更改为B。

题目大意就是这样,然后这道题呢,就是一道线段树的区间查询与端点更新的问题

与区间和有所不同的是:这道题我们是维护线段树的最大值,所以在建树的时候,pushup时,我们要对父节点维护的是两个子节点中的最大值。

然后最后再注意一下更新的时候别忘记了要pushup来更新父节点。

#include<stdio.h>#include<string.h>#include<iostream>#include<algorithm>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<l) query(l,r,temp+1);    else{        query(l,mid,temp);        query(mid+1,r,temp+1);    }}void update(int v,int pos,int score){    if(tree[v].l==pos&&tree[v].r==pos){        tree[v].val=score;        return;    }    int temp=v<<1;    int mid=(tree[v].l+tree[v].r)>>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);            }        }    }}


上一篇:hdu(1698)——Just a Hook(成段更新,节点求和,lazy思想)
下一篇:hdu(1166)——敌兵布阵(更新节点,区间求和)