题解 P1198 【[JSOI2008]最大数】

八重樱 · 2017-10-26 22:00:58 · 题解

/* ZKW线段树真心好用啊~

刚刚学ZKW

就一遍过了这道题

全程零递归

手动模拟很方便

*/

#include<cstdio>
using namespace std;
inline int intin(){register char c=getchar();while(c!=45&&(c<48||c>57))c=getchar();register int a=0;register bool b=0;if(c==45){c=getchar();b=1;}while(c>47&&c<58){a=(a<<1)+(a<<3)+c-48;c=getchar();}if(b)a*=(-1);return a;}
inline void intot(int a){if(a<0){putchar(45);a*=(-1);}if(a>9)intot(a/10);putchar(a%10+48);}
inline bool xin(){register char c=getchar();while(c!='A'&&c!='Q')c=getchar();if(c=='A')return 1;return 0;}
inline int mmx(int a,int b){if(a>b)return a;return b;}
int    mx[524288];//树 
int main()
{
    int q=intin(),md=intin(),t=0,n=262144,m=262143;
    for(int i=n;i<=n<<1;i++)mx[i]=-2147483644;//初始化 
    while(q--)
    {
        if(xin())
        {
            mx[++m]=(intin()+t)%md;//更新点 
            int r=m>>1;
            while(r){mx[r]=mmx(mx[r<<1],mx[r<<1|1]);r=r>>1;}//从此点向上更新 
        }else{
            int l=m-intin(),r=m+1;t=-2147483645;//ZKW线段树查询开区间(l-1,r+1)比闭区间[l,r]方便
            while(l^r^1)//ZKW线段树区间查询标准写法 
            {
                if(~l&1)if(t<mx[l^1])t=mx[l^1];
                if(r&1)if(t<mx[r^1])t=mx[r^1];
                l=l>>1;r=r>>1;
            }
            intot(t);putchar('\n');
        }
    }
    return 0;
}