记录编号	442791	评测结果	AAAAAAAAAA
题目名称	[JSOI 2008] 最大数	最终得分	100
用户昵称	swttc	是否通过	通过
代码语言	C++	运行时间	2.331 s
提交时间	2017-08-28 17:01:54	内存使用	6.42 MiB

#include<iostream>
#include<cstdio>

using namespace std;

long long m,d,cnt,maxx[800010],t;

void add(long long l,long long r,long long o,long long p,long long x)
{//cout<<l<<" "<<r<<endl;system("pause");
	if(l==r)
	{
		if(l==p)
		{//cout<<"sss"<<x<<endl;
			maxx[o]+=x;
		}
		return;
	}
	long long ls=o*2;
	long long rs=o*2+1;
	long long mid=(l+r)>>1;
	if(mid>=p) add(l,mid,ls,p,x);
	if(mid<p)  add(mid+1,r,rs,p,x);
	maxx[o]=max(maxx[ls],maxx[rs]);
	return;
}

long long query(long long l,long long r,long long o,long long ll,long long rr)
{//
	long long maxt=-1;
	if(ll<=l&&rr>=r)
	{
		return maxx[o];
	}
	long long ls=o*2;
	long long rs=o*2+1;
	long long mid=(l+r)>>1;
	if(mid>=ll)
	{
		maxt=max(maxt,query(l,mid,ls,ll,rr));
	}
	if(mid<rr)
	{
		maxt=max(maxt,query(mid+1,r,rs,ll,rr));
	}
	return maxt;
}

int main()
{
	freopen("bzoj_1012.in","r",stdin);
	freopen("bzoj_1012.out","w",stdout);
	//freopen("1.txt","r",stdin);
	//freopen("2.txt","w",stdout);
	scanf("%lld%lld",&m,&d);
	for(long long i=1;i<=m;i++)
	{
		char c;
		long long n;
		cin>>c;
		scanf("%lld",&n);//cout<<" "<<n%d<<endl;//system("pause");
		if(c=='A')
		{//cout<<"ttt"<<t<<endl;
			add(1,m,1,++cnt,(n+t)%d);
		}
		else
		{
			t=query(1,m,1,cnt-n+1,cnt);
			printf("%lld\n",t);
		}
	}
	return 0;
}