记录编号	179775	评测结果	AAAAAAAAAA
题目名称	[JSOI 2008] 最大数	最终得分	100
用户昵称	炽烈的爱	是否通过	通过
代码语言	C++	运行时间	4.029 s
提交时间	2015-08-17 10:45:27	内存使用	3.33 MiB

#include<cstdio>
#include<iostream>
#include<string>
using namespace std;
# define ll long long
ll yy;
ll n,m,l,r;
ll aa[200010],q[200010];
void get(int x)
{
	ll j=l,k=r,mid;
	while(j<=k)
	{
		mid=(j+k)>>1;
		if(x<=q[mid])
		{
			k=mid-1;
			yy=mid;
		}
		else
		    j=mid+1;
	}
	yy=aa[q[yy]];
}
int main()
{
	freopen("bzoj_1012.in","r",stdin);
	freopen("bzoj_1012.out","w",stdout);
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;++i)
	{
		char ch;ll x;
		cin>>ch>>x;
		if(ch=='A')
		{
			x=(x+yy)%m;
			aa[++aa[0]]=x;
			while(l<r&&aa[q[r]]<=aa[aa[0]])
			    r--;
			q[++r]=aa[0];
		}
		else
		{
			x=aa[0]-x+1;
			get(x);
			printf("%lld\n",yy);
		}
	}
	//while(1);
}