【题解】Luogu P1198 【[JSOI2008]最大数】

这题其实用线段树就蛮好做的，其实都不用建树，不过要注意可能有输入为0的序列，这时候就会变得特别坑，然后我提交了好多次才解决的。

#include<cstdio>

const int MAXN = 200000 + 6;

int a[MAXN];

class SegmentTree{
    public:int l,r;
    public:int max;
};
SegmentTree 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;
        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 m,d;
    scanf("%d %d\n",&m,&d);
    
    int ans = 0,j = 0;
    
    for(int i = 1;i <= m;i++){
        a[i] = -0x7fffffff;
    }
    
    build(1,1,m);
    
    while(m--){
        char op;
        int key;
        scanf("%c %d\n",&op,&key);
        
        if(op == 'A'){
            j++;
            change(1,j,(key + ans) % d);
        }else{
            if(key == 0){
                ans = 0;
            }else{
                ans = ask(1, j - key + 1,j) % d;
            }
            
            printf("%d\n",ans);
        }
    }
        
    return 0;
}