记录编号	272843	评测结果	AAAAAAAAAA
题目名称	[JSOI 2008] 最大数	最终得分	100
用户昵称	Hzoi_	是否通过	通过
代码语言	C++	运行时间	1.068 s
提交时间	2016-06-18 09:09:17	内存使用	4.48 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#define lch l,mid,rt<<1
#define rch mid+1,r,rt<<1|1
using namespace std;
const int maxn=200010;
void add(int,long long,int,int,int);
long long query(int,int,int,int,int);
int n=0,m;
long long a[maxn<<2]={0},ans=0,d,x;
char c;
inline int MAIN(){
#define MINE
#ifdef MINE
	freopen("bzoj_1012.in","r",stdin);
	freopen("bzoj_1012.out","w",stdout);
#endif
	scanf("%d%lld",&m,&d);
	for(int i=0;i<m;i++){
		scanf(" %c%lld",&c,&x);
		if(c=='Q'){
			ans=query(n-x+1,n,1,m,1);
			printf("%lld\n",ans);
		}
		else if(c=='A')add(++n,(x+ans)%d,1,m,1);
	}
	return 0;
}
inline void add(int x,long long num,int l,int r,int rt){
	if(l==r){
		a[rt]+=num;
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid)add(x,num,lch);
	else add(x,num,rch);
	a[rt]=max(a[rt<<1],a[rt<<1|1]);
}
inline long long query(int s,int t,int l,int r,int rt){
	if(s<=l&&t>=r)return a[rt];
	int mid=(l+r)>>1;
	if(t<=mid)return query(s,t,lch);
	if(s>mid)return query(s,t,rch);
	return max(query(s,t,lch),query(s,t,rch));
}
int haha=MAIN();
int main(){;}