学步园

入门线段树题

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define Lson  l,m,rt<<1
#define Rson  m+1,r,rt<<1|1
int const MAXN = 200010;
int n,m;
struct Tree{
    int l,r;
    int v;
}tree[MAXN * 4];
inline int Max(int a,int b){
    return a>b?a:b;
}
inline void PushUp(int rt){
    tree[rt].v = Max(tree[rt<<1].v,tree[rt<<1|1].v);
}
void Build(int l,int r,int rt){
    tree[rt].l = l;
    tree[rt].r = r;
    if(l == r){
        scanf("%d",&tree[rt].v);
        return ;
    }
    int m = (l + r)>>1;
    Build(Lson);
    Build(Rson);
    PushUp(rt);
}
void Update(int p,int s,int l,int r,int rt){
    if(l == r){
        tree[rt].v = s;
        return ;
    }
    int m = (l + r)>>1;
    if(p <= m) Update(p,s,Lson);
    else Update(p,s,Rson);
    PushUp(rt);
}
int Query(int L,int R,int l,int r,int rt){
    if(L <= l && r <= R){
        return tree[rt].v;
    }
    int m =(l + r)>>1;
    int ret = 0;
    if(L <= m) ret = Max(ret,Query(L,R,Lson));
    if(R > m) ret = Max(ret,Query(L,R,Rson));
    return ret;
}
int main(){
    while(~scanf("%d%d",&n,&m)){
        Build(1,n,1);
        for(int i = 0;i < m;i++){
            char str[3];
            int a,b;
            scanf("%s%d%d",str,&a,&b);
            if(str[0] == 'Q') printf("%d\n",Query(a,b,1,n,1));
            else Update(a,b,1,n,1);
        }
        /*for(int i = 1;i <= n * 2;i++){
            cout<<tree[i].v<<endl;
        }*/
    }
    return 0;
}