Cogs 1844. [JSOI2008]最大数maxnumber

/*

区间修改+求区间max.

*/

#include<iostream>

#include<cmath>

#include<cstdio>

#define LL long long

#define MAXN 200001

using namespace std;

LL n,m,cut,mod;

struct data{

    LL l,r,lc,rc,sum,bj;

}tree[MAXN*4];

LL read(){

    LL x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();

    return x*f;

}

void build(LL l,LL r){

    LL k=++cut;

    tree[k].l=l,tree[k].r=r;

    if(l==r){

        tree[k].sum=0;

        return ;

    }

    LL mid=(l+r)>>1;

    tree[k].lc=cut+1;

    build(l,mid);

    tree[k].rc=cut+1;

    build(mid+1,r);

}

void change(LL k,LL p,LL add){

    if(tree[k].l==tree[k].r&&tree[k].l==p){

        tree[k].sum=add;

        return ;

    }

    LL mid=(tree[k].l+tree[k].r)>>1;

    if(p<=mid) change(tree[k].lc,p,add);

    else if(p>mid) change(tree[k].rc,p,add);

    tree[k].sum=max(tree[tree[k].lc].sum,tree[tree[k].rc].sum);

}

LL query(LL k,LL l,LL r){

    if(l<=tree[k].l&&tree[k].r<=r) return tree[k].sum;

    LL tot=-0x7fffffff;

    LL mid=(tree[k].l+tree[k].r)>>1;

    if(r<=mid) tot=max(query(tree[k].lc,l,r),tot);

    else if(l>mid) tot=max(query(tree[k].rc,l,r),tot);

    else tot=max(max(query(tree[k].lc,l,mid),query(tree[k].rc,mid+1,r)),tot);

    return tot;

}

int main(){

    freopen("bzoj_1012.in","r",stdin);

    freopen("bzoj_1012.out","w",stdout);

    LL x,y,z,p=0;

    char ch;

    m=read();mod=read();build(1,m);

    for(int i=1;i<=m;i++){

        cin>>ch;x=read();

        if(ch=='A') change(1,++n,(x+p+mod)%mod);

        else {

            p=query(1,n-x+1,n);

            cout<<p;printf("\n");

        }

    }

    return 0;

}