BZOJ1012: [JSOI2008]最大数maxnumber

 1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 #include<stdlib.h> 5 //#include<queue> 6 //#include<math.h> 7 //#include<time.h> 8 //#include<iostream> 9 using namespace std;10 11 int n,mod;12 #define maxn 20001113 struct BIT14 {15 ????int a[maxn],n;16 ????void clear(int m) {n=m; for (int i=1;i<=n;i++) a[i]=-0x7fffffff;}17 ????void add(int x,int v) {for (;x<=n;x+=x&-x) a[x]=max(a[x],v);}18 ????int query(int x) {int ans=0; for (;x;x-=x&-x) ans=max(ans,a[x]); return ans;}19 }t;20 21 struct Point{int x; bool w;}a[maxn];22 int main()23 {24 ????scanf("%d%d",&n,&mod);25 ????char id[5];26 ????int tot=0;27 ????for (int i=1;i<=n;i++)28 ????{29 ????????scanf("%s%d",id,&a[i].x);30 ????????a[i].w=(id[0]==‘A‘);31 ????????tot+=(id[0]==‘A‘);32 ????}33 ????t.clear(tot);34 ????int last=0;35 ????for (int i=1;i<=n;i++)36 ????{37 ????????if (a[i].w) t.add(tot--,(a[i].x+0ll+last)%mod);38 ????????else printf("%d\n",(last=t.query(tot+a[i].x)));39 ????}40 ????return 0;41 }