记录编号	324175	评测结果	AAAAAAAAAA
题目名称	[JSOI 2008] 最大数	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.668 s
提交时间	2016-10-17 20:28:41	内存使用	0.31 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <cctype>
#include <list>
#include <vector>
using namespace std;
typedef long long LL;
int fast_read()
{
    int r;
    char c;
    bool sig = false;
    while(c = getchar())    
    {
        if(c >= '0' && c <= '9')
        {
            r = c^0x30;
            break;
        }else if(c == '-')sig = true;
    }
    while(isdigit(c = getchar()))
        r = (r<<3)+(r<<1)+(c^0x30);
    return sig? -r:r;
}
LL fast_readLL()
{
    LL r;
    char c;
    bool sig = false;
    while(c = getchar())    
    {
        if(c >= '0' && c <= '9')
        {
            r = c^0x30;
            break;
        }else if(c == '-')sig = true;
    }
    while(isdigit(c = getchar()))
        r = (r<<3)+(r<<1)+(c^0x30);
    return sig? -r:r;
}
#define SIZE(x) ((x)?(x)->size:0)
struct node
{
    node *ch[2];
    int size;
    LL data;
    LL maxv;
    node(LL v):data(v), maxv(v), size(1)
    {
        ch[0] = ch[1] = NULL;
    }
    void momomo()
    {
        size = 1;
        maxv = data;
        for(int i = 0; i <= 1; i++)
        {
            if(ch[i])
            {
                size += ch[i]->size;
                maxv = max(maxv, ch[i]->maxv);
            }
        }
    }
    inline int cmp(int s)
    {
        if(s == SIZE(ch[0])+1)return -1;
        return s > SIZE(ch[0])+1;
    }
    inline void setv(LL v)
    {
        data = maxv = v;
        momomo();
    }
};
//d = 0 LL旋转
//d = 1 RR旋转
void rotate(node *&o, int d)
{
    node *k = o -> ch[d];
    o -> ch[d] = k -> ch[d^1];
    k -> ch[d^1] = o;
    o -> momomo();
    k -> momomo();
    o = k;
}
//spaly 读起来比 splay好听
void spaly(node *&o, int k)
{
    if(!o)return;
    int d = o -> cmp(k);
    if(d == -1)return;
    if(d)
        k -= SIZE(o->ch[0])+1;
    node *&p = o -> ch[d];
    int d2 = p->cmp(k);
    if(~d2)
    {
        if(d2)k -= SIZE(p->ch[0])+1;
        spaly(p->ch[d2], k);
        if(d == d2)
            rotate(o, d);
        else
            rotate(p, d2);
    }
    rotate(o, d);
}
int main()
{
    freopen("bzoj_1012.in", "r", stdin);
    freopen("bzoj_1012.out", "w", stdout);
    node *t = new node(0);
    t -> ch[1] = new node(0);
    t -> momomo();
    
    int n;
    LL D;
    n = fast_read();
    D = fast_readLL();
    int len = 0;
    LL last = 0;
    while(n--)
    {
        char c;
        while(!isalpha(c = getchar()));
        if(c == 'Q')
        {
            int arg = fast_read();
            int r = len;
            int l = len-arg+1;
            spaly(t, l);
            spaly(t->ch[1], r-l+2); 
            last = t->ch[1]->ch[0]->maxv;
            printf("%lld\n", last);
        }else if(c == 'A')
        {
            LL tmp = (fast_readLL()%D+last%D)%D;
            spaly(t, len+2);
            t -> ch[1] = new node(0);
            t -> setv(tmp);
            len++;
        }
    }
    return 0;
}