记录编号	182567	评测结果	AAAAAAAAAA
题目名称	[JSOI 2008] 最大数	最终得分	100
用户昵称	一個人的雨	是否通过	通过
代码语言	C++	运行时间	2.831 s
提交时间	2015-08-28 15:04:40	内存使用	26.03 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define speedup ios::sync_with_stdio(false)
using namespace std;
const int maxn=1050;
const long long inf=1e20;
struct BLOCK{
	int id;
	long long num;
}p[maxn*3000];
long long maxx[maxn*100];
int cnt=0,m,L;
int blength=1000,block=1,pos=0;
long long t=0,D;

int main()
{
	freopen("bzoj_1012.in","r",stdin);
	freopen("bzoj_1012.out","w",stdout);
	speedup;
	for (int i=1;i<=100000;++i) maxx[i]=-inf;
	cin>>m>>D;
	char ch; int y,z;
	long long x;
	for (int i=1;i<=m;++i){
		cin>>ch;
		if (ch=='A'){
			if (pos==blength){pos=1;block++;} else pos++;
			p[++cnt].id=block; cin>>x; p[cnt].num=(x+t)%D;
			maxx[block]=max(maxx[block],p[cnt].num);
		}
		else if (ch=='Q'){
			cin>>L;
			long long ans=-inf;
			if (L<pos){
				for (int j=cnt;j>=cnt-L+1;--j){
					if (p[j].id<block) break;
					ans=max(ans,p[j].num);
				}
				cout<<ans<<endl;
			}
			else if (L==pos) {
				ans=maxx[block];
				cout<<maxx[block]<<endl;
			}
			else if (L>pos){
				ans=maxx[block];
				x=block; L-=pos; y=cnt-pos;
				while (L>=blength){
					ans=max(ans,maxx[--x]);
					L-=blength; y-=blength;
				}
				z=p[y].id;
				if (L)
					for (int j=y;j>=y-L+1;--j){
						ans=max(ans,p[j].num);
						if (p[j].id<z) break;
					}
				cout<<ans<<endl;
			}
			t=ans;
		}
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}