hdu1754 I Hate It

傳送門

思路

裸題

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 200010;

int w[N];
int n,m;
struct node{
    int l,r;
    int maxm;
}tr[N*4];

void pushup(int u){
    tr[u].maxm=max(tr[u<<1].maxm,tr[u<<1|1].maxm);
}

void build(int u,int l,int r){
    tr[u]={l,r};
    if(l==r) tr[u].maxm=w[l];
    else{
        int mid=l+r>>1;
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);
        pushup(u);
    }
}

int query(int u,int l,int r){
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u].maxm;
    
    int mid=tr[u].l+tr[u].r>>1;
    int res=-1e9;
    if(l<=mid) res=query(u<<1,l,r);
    if(r>mid) res=max(res,query(u<<1|1,l,r));
    
    return res;
}

void modify(int u,int pos,int v){
    if(tr[u].l==pos&&tr[u].r==pos) tr[u].maxm=v;
    else{
        int mid=tr[u].l+tr[u].r>>1;
        if(pos<=mid) modify(u<<1,pos,v);
        else modify(u<<1|1,pos,v);
        pushup(u);
    }
}

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