[置顶] HDU 1754 线段树

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<iomanip>

#define Lson  left , t   , rt<<1
#define Rson  t+1  ,right,rt<<1|1

using namespace std;
const int maxn=200005;
int f[maxn<<2];

void PushUP( int rt ){
    f[rt] = max( f[rt<<1], f[rt<<1|1] );
}

void build( int left, int right ,int rt ){
    if( left==right ){
        cin>>f[rt];
        return;
    }
    int t=(left + right)>>1;
    build(Lson);
    build(Rson);
    PushUP(rt);
}

void update(int ii,int value,int left, int right, int rt ){
    if( left == right ){
        f[rt] = value; return;
    }
    int t=(left+right)>>1;
    if(ii<=t) update(ii, value, Lson);
    else      update(ii, value, Rson);
    PushUP(rt);
}

int query(int l, int r, int left, int right, int rt ){
    if( l<=left && r>=right )
        return f[rt];
    int t=(left+right)/2;
    int ret = 0;
    if(l <= t)ret = max(ret, query( l, r, Lson) );
    if(r > t) ret = max(ret, query( l, r, Rson) );
    return ret;
}

int main(){
    int n,m;
    while(cin>>n>>m){
        build(1,n,1);
        while(m--){
            char C; int a,b;//for(int i=0;i<=n;++i)cout<<f[i]<<' ';cout<<endl;
            cin>>C>>a>>b;
            if(C=='Q') cout<<query(a,b,1,n,1)<<endl;
            else update(a,b,1,n,1);
        }
    }
    return 0;
}