记录编号	398354	评测结果	AAAAAAAAAA
题目名称	[JSOI 2008] 最大数	最终得分	100
用户昵称	Fisher.	是否通过	通过
代码语言	C++	运行时间	3.168 s
提交时间	2017-04-22 07:31:22	内存使用	12.52 MiB

#include <iostream>
#include <cstdio>
#include <iomanip>
#include <cstring>
#include <algorithm>
#include <cmath>
#define ll long long
using namespace std;
const ll maxn=200010;
ll n,d,mem;
ll len;
struct q
{
	ll maxx;
};
q node[maxn*8];
inline void insert(ll o,ll l,ll r,ll nl,ll nr,ll data)
{
	if(l>=nl&&r<=nr)
	{
		node[o].maxx=data;
		return;
	}
	ll m=(l+r)/2;
	if(m>=nl)
	{
		insert(o*2,l,m,nl,nr,data);
	}
	if(m<nr)
	{
		insert(o*2+1,m+1,r,nl,nr,data);
	}
	node[o].maxx=max(node[o*2].maxx,node[o*2+1].maxx);
}
inline ll find(ll o,ll l,ll r,ll nl,ll nr)
{
	if(l>=nl&&r<=nr)
	{
		//mem=max(mem,node[o].maxx);    //错在这里，因为记忆变量会被多次调用，所以改变了，就是那种所需区间也被分割的情况！
		return node[o].maxx;
	}
	ll m=(l+r)/2;
	ll ans=-0x7fffffff;
	if(m>=nl)
	{
		ans=max(ans,find(o*2,l,m,nl,nr));
	}
	if(m<nr)
	{
		ans=max(ans,find(o*2+1,m+1,r,nl,nr));
	}
	return ans;
}
int main()
{
	freopen("bzoj_1012.in","r",stdin);
	freopen("bzoj_1012.out","w",stdout);
	cin>>n>>d;
	ll t=n;
	while(t--)
	{
		char a;
		ll x;
		cin>>a>>x;
		if(a=='A')
		{
			len++;
			n++;
			insert(1,1,maxn,len,len,(x+mem)%d);
		}
		if(a=='Q')
		{
			mem=find(1,1,maxn,len-x+1,len);
			cout<<mem<<endl;
			//cout<<len<<endl;
		}
	}
	return 0;
}