记录编号	269253	评测结果	AAAAAAAAAA
题目名称	[JSOI 2008] 最大数	最终得分	100
用户昵称	Marvolo	是否通过	通过
代码语言	C++	运行时间	0.557 s
提交时间	2016-06-13 13:34:52	内存使用	20.34 MiB

#include<cstdio>
#include<iostream>
using namespace std;

long long i,n,l,cnt,tt,d;
char c[200010];
long long a[200010];
struct {
	long long l,r,d;
}t[800040];

inline long long max(long long a,long long b){return (a>b)?a:b;}

void maketree(long long x,long long low,long long high){
	long long mid=0;
	t[x].l=low;	t[x].r=high;
	if (low==high)	return;
	mid=(low+high)/2;
	maketree(x*2,low,mid);	maketree(x*2+1,mid+1,high);
	return;
}

void insert(int x,int low,long long k){
	long long mid=0;
	t[x].d=max(t[x].d,k);
	if (t[x].l==t[x].r)	return;
	mid=(t[x].l+t[x].r)/2;
	if (low<=mid)	insert(x*2,low,k);	else insert(x*2+1,low,k);
	return;
}

long long query(long long x,long long low,long long high){
	long long mid=0;
	if (t[x].l==low&&t[x].r==high)	return t[x].d;
	if (t[x].l==t[x].r)	return t[x].d;
	mid=(t[x].l+t[x].r)/2;
	if (high<=mid)	return query(x*2,low,high);	else
	if (low>mid)	return query(x*2+1,low,high);	else
	return max(query(x*2,low,mid),query(x*2+1,mid+1,high));
}

inline long long read(){
	long long x=0,p=0;
	while (p-48<0||p-48>9)	p=getchar();
	while (p-48>=0&&p-48<=9)	{x=x*10+p-48;	p=getchar();}
	return x;
}

int main(){
	freopen("bzoj_1012.in","r",stdin);
	freopen("bzoj_1012.out","w",stdout);
	scanf("%lld%lld",&n,&d);
	for (i=1;i<=n;i++){
		c[i]=getchar();
		while (c[i]!='A'&&c[i]!='Q')	c[i]=getchar();
		if (c[i]=='A')	l++;
		a[i]=read();	}
	maketree(1,1,l);
	tt=0;	cnt=0;
	for (i=1;i<=n;i++) {
		if (c[i]=='A')	{
			long long p=(a[i]+tt)%d;
			insert(1,++cnt,p);
		}
		else {	tt=query(1,cnt-a[i]+1,cnt);
				printf("%lld\n",tt);	}
		}
	return 0;
}