HDU 1754 I Hate It(区间查询+单点修改)

const int N=2e5+5;
 
    int n,m,t;
    int i,j,k;
    int a[N];
    struct Node
    {
        int l,r;
        int maxx;
    }node[N<<2];

void push_up(int id)
{
    node[id].maxx=max(node[id<<1].maxx,node[id<<1|1].maxx);
}

void build(int l,int r,int id)
{
    node[id].l=l,node[id].r=r;
    node[id].maxx=-inf;
    if(l==r){
        node[id].maxx=a[l];
    } else{
        int mid=l+r>>1;
        build(l,mid,id<<1);
        build(mid+1,r,id<<1|1);
        push_up(id);
    }
}

void update(int pos,int val,int id)
{
    int L=node[id].l,R=node[id].r;

    if(pos==L && pos==R){
        node[id].maxx=val;
    } else{
        int mid=L+R>>1;
        if(mid>=pos) update(pos,val,id<<1);
        else update(pos,val,id<<1|1);
        push_up(id);
    }
}

int query(int l,int r,int id)
{
    int L=node[id].l,R=node[id].r;
    if(L>=l && r>=R){
        return node[id].maxx;
    } else{
        int mid=L+R>>1;
        int ans=-inf;
        if(mid>=l) ans=max(ans,query(l,r,id<<1));
        if(r>=mid+1) ans=max(ans,query(l,r,id<<1|1));
        return ans;
    }
}

int main()
{
    //IOS;
    while(~sdd(n,m)){
        for(i=1;i<=n;i++) sd(a[i]);
        build(1,n,1);
        int x,y; char ch[10];
        while(m--){
            ss(ch);
            sdd(x,y);
            if(ch[0]=='Q'){
                pd( query(x,y,1) );
            } else if(ch[0]=='U'){
                update(x,y,1);
            }
        }
    }
    //PAUSE;
    return 0;
}