【题解】Luogu P1531 【I Hate It】

这里也是蛮裸的一道线段树,维护区间最值就好了,输出注意看一下题。

#include<cstdio>
#include<iostream>

namespace OI{
    using std::cin;
}
using namespace OI;

const int MAXN = 200000 + 6;
int a[MAXN];

class Segment{
    public:int l,r;
    public:int max;
};
Segment t[MAXN * 4];

inline int LEFT(int x){return x << 1;}
inline int RIGHT(int x){return x << 1 | 1;}
inline int MID(int l,int r){return (l + r) >> 1;}
inline int max(int a,int b){return a > b ? a : b;}

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;
    }
    build(LEFT(p),l,MID(l,r));
    build(RIGHT(p),MID(l,r) + 1,r);
    t[p].max = max(t[LEFT(p)].max,t[RIGHT(p)].max);
}

void change(int p,int x,int v){
    if(t[p].l == t[p].r){
        //t[p].max = v;
        t[p].max = max(t[p].max,v);
        return;
    }
    if(x <= MID(t[p].l,t[p].r)){
        change(LEFT(p),x,v);
    }else{
        change(RIGHT(p),x,v);
    }
    t[p].max = max(t[LEFT(p)].max,t[RIGHT(p)].max);
}

int ask(int p,int l,int r){
    if(l <= t[p].l && r >= t[p].r){
        return t[p].max;
    }
    int ans = -0x7fffffff;
    if(l <= MID(t[p].l,t[p].r)){
        ans = max(ans,ask(LEFT(p),l,r));
    }
    if(r > MID(t[p].l,t[p].r)){
        ans = max(ans,ask(RIGHT(p),l,r));
    }
    return ans;
}

int main(){
    int n,m;
    scanf("%d %d\n",&n,&m);
    
    for(int i = 1;i <= n;i++){
        scanf("%d",&a[i]);
    }
    
    build(1,1,n);
    
    while(m--){
        char op;
        int a,b;
        cin >> op >> a >> b;
        
        if(op == 'Q'){
            printf("%d\n",ask(1,a,b));
        }else{
            change(1,a,b);
        }
    }
    
    return 0;
}