P1198 [JSOI2008]最大数

5 100
A 96
Q 1
A 97
Q 1
Q 2

96
93
96

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #define lglg long long int
 6 using namespace std;
 7 const int n=200001;
 8 lglg mod,m;
 9 struct node
10 {
11     lglg l,r,w;
12 }tree[n*4];
13 lglg num=1;
14 lglg last=0;
15 lglg ans=-1;
16 void updata(int k)
17 {
18     tree[k].w=max(tree[k*2].w,tree[k*2+1].w);
19 }
20 void build(int ll,int rr,int k)
21 {
22     tree[k].l=ll;tree[k].r=rr;
23     if(tree[k].l==tree[k].r)
24     {
25         tree[k].w=0;
26         return ;
27     }
28     int m=(ll+rr)/2;
29     build(ll,m,k*2);
30     build(m+1,rr,k*2+1);
31     updata(k);
32 }
33 int read(lglg &x)
34 {
35     int flag=0;
36     char c=getchar();x=0;
37     if(c=='-')flag=1;
38     while(c<'0'||c>'9')c=getchar();
39     while(c>='0'&&c<='9')x=x*10+c-48,c=getchar();
40     return flag==1?x=-x:x;    
41 }
42 void point_add(int where,int p,int k)
43 {
44     if(tree[k].l==tree[k].r)
45     {
46         tree[k].w=p;
47         return ;
48     }
49     int m=(tree[k].l+tree[k].r)/2;
50     if(where<=m)
51         point_add(where,p,k*2);
52     else
53         point_add(where,p,k*2+1);
54     updata(k);    
55 }
56 void interval_ask(int ll,int rr,int k)
57 {
58     if(ll<=tree[k].l&&rr>=tree[k].r)
59     {
60         if(ans<tree[k].w)ans=tree[k].w;
61         return ;
62     }
63     int m=(tree[k].l+tree[k].r)/2;
64     if(ll<=m)
65         interval_ask(ll,rr,k*2);
66     if(rr>=m+1)
67         interval_ask(ll,rr,k*2+1);
68 }
69 int main()
70 {
71     //read(m);read(mod);
72     cin>>m>>mod;
73     build(1,n,1);
74     for(int i=1;i<=m;i++)
75     {
76         char c;
77         cin>>c;
78         if(c=='A')
79         {
80             lglg p;
81             //read(p);
82             cin>>p;
83             p=(p+last)%mod;
84             point_add(num++,p,1);
85         }
86         else
87         {
88             lglg p;
89             ans=-1;
90             //read(p);
91             cin>>p;
92             interval_ask(num-p,num-1,1);
93             last=ans%mod;
94             printf("%lld\n",ans);
95         }
96     }
97     return 0;
98 }