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

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
LL sum[1000005],d,maxn,l;
int num,n,c;
char ch;
void build(int aq,LL bw,int x,int y,int z)
{
	if(x==y){
		sum[z]=bw;
		return;
	}
	int mid=(x+y)>>1;
	if(mid>=aq) build(aq,bw,x,mid,z<<1);
	else build(aq,bw,mid+1,y,z<<1|1);
	sum[z]=max(sum[z<<1],sum[z<<1|1]);
}
LL getmaxn(int le,int re,int x,int y,int z)
{
	if(le<=x&&re>=y)
	  return sum[z];
	int mid=(x+y)>>1;
	LL ans=0;
	if(le<=mid)
	  ans=max(ans,getmaxn(le,re,x,mid,z<<1));
	if(mid<re)
	  ans=max(ans,getmaxn(le,re,mid+1,y,z<<1|1));
	return ans;
}
int main()
{   freopen("bzoj_1012.in","r",stdin);
    freopen("bzoj_1012.out","w",stdout);
	scanf("%d%lld",&num,&d);
	for(int i=1;i<=num;++i)
	{
		scanf("%s%lld",&ch,&l);
		if(ch=='A')
		{   n++;
			build(n,(l+maxn)%d,1,200001,1);
		}
		if(ch=='Q')
		{   
			maxn=getmaxn(n-l+1,n,1,200001,1);
			printf("%lld\n",maxn);
		}
	}
}