hdu1754线段树 单点更改 区间求最值

题目传送 hdu1754

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+10;
int mx[maxn*2],a[maxn];
int N,M,ans;
int b,c;
int build(int l,int r,int root){
    if(l==r)return mx[root]=a[l];
    else{
        int mid=(l+r)/2;
        return mx[root]=max(build(l,mid,root*2),build(mid+1,r,root*2+1));        
    }
}
void updt(int l,int r,int root){
        
    if(l==r){
        mx[root]=c;
        return;
    }
    else{
        mx[root]=max(mx[root],c);
        int mid=(l+r)/2;
        if(b<=mid)updt(l,mid,root*2);
        else updt(mid+1,r,root*2+1);
    }
}
int quemax(int l,int r,int root){
    if(b<=l&&r<=c){
        return ans=max(ans,mx[root]);
    }
    else{
        int mid=(l+r)/2;
        if(b<=mid) ans= max(ans, quemax(l,mid,root*2));
        if(c>=mid+1) ans = max(ans, quemax(mid+1,r,root*2+1));       
    }
    return ans;
}
int main(){
    char s[10];
    while(scanf("%d%d",&N,&M)!=EOF){
        for(int i=1;i<=N;i++){
            scanf("%d",&a[i]);
        }
        build(1,N,1);
        for(int j=1;j<=M;j++){                 
            scanf("%s%d%d",s,&b,&c);
            if(s[0]=='Q'){
                ans=-1e9;
                quemax(1,N,1);
                printf("%d\n",ans);
            }
            if(s[0]=='U'){
                updt(1,N,1);
            }
        }
    }
    return 0;
}