【题解】HDOJ P1754【I Hate it】

背景

这里应该算是双倍经验,但是调了好久,因为build()函数写挂了,主要是$l$和$1$这两个字符太像了

分析

这里就是一个裸的板,没啥好分析的

代码

#include<cstdio>

const int MAXN = 2000000 + 6;
int A[MAXN * 8];

class SegmentTree{
    public:int l,r;
    public:int max;
};SegmentTree t[MAXN * 8];
inline int L(int x){return x << 1;}inline int R(int x){return x << 1 | 1;}
inline int max(int a,int b){return a > b ? a : b;}
inline void maintain(int p){t[p].max = max(t[L(p)].max,t[R(p)].max);}
void build(int p,int l,int r){
    t[p].l = l;t[p].r = r;
    if(l == r){t[p].max = A[l];return;}
    int mid = (l + r) >> 1;
    build(L(p),l,mid);
    build(R(p),mid + 1,r);
    maintain(p);
}
void change(int p,int x,int v){
    if(t[p].l == t[p].r){t[p].max = v;return;}
    int mid = (t[p].l + t[p].r) >> 1;
    if(x <= mid) change(L(p),x,v);
    else change(R(p),x,v);
    maintain(p);
}
int ask(int p,int l,int r){
    if(l <= t[p].l && r >= t[p].r) return t[p].max;
    int ans = -0x7fffffff,mid = (t[p].l + t[p].r) >> 1;
    if(l <= mid) ans = max(ans,ask(L(p),l,r));
    if(r > mid) ans = max(ans,ask(R(p),l,r));
    return ans;
}

int main(){
    int n,m;
    while(scanf("%d %d",&n,&m) != EOF){
        for(int i = 1;i <= n;i++) scanf("%d",&A[i]);
        build(1,1,n);char op[6];int l,r;
        while(m--){
            scanf("%s %d %d",op,&l,&r);
            if(op[0] == 'Q') printf("%d\n",ask(1,l,r));
            else change(1,l,r);
        }
    }
    return 0;
}