记录编号	144089	评测结果	AAAAAAAAAA
题目名称	[JSOI 2008] 最大数	最终得分	100
用户昵称	Foenix	是否通过	通过
代码语言	C++	运行时间	0.499 s
提交时间	2014-12-20 12:17:09	内存使用	8.71 MiB

#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
typedef long long LL;
const int MAXN=200005;
const int INF=(1<<29);
LL T[MAXN*3],m,len=0,x,M,t,D;
char ch;
struct NODE{
	char ch;
	LL x,len;//len records now length
}A[MAXN];
void change(int i,LL t){
	for(i+=M,T[i]=t,i>>=1;i;i>>=1){
		T[i]=max(T[i<<1],T[(i<<1)^1]);
	}
}
LL Query_max(int s,int t){
	LL ans=-INF;
	for(s=s+M-1,t=t+M+1;s^t^1;s>>=1,t>>=1){
		if(~s&1)ans=max(ans,T[s^1]);
		if( t&1)ans=max(ans,T[t^1]);
	}
	return ans;
}
int main(){
	freopen("bzoj_1012.in","r",stdin);
	freopen("bzoj_1012.out","w",stdout);
	scanf("%lld%lld",&m,&D);
	for(int i=1;i<=m;i++){
		cin>>ch;scanf("%lld",&x);
		A[i].ch=ch; A[i].x=x;
		if(ch=='A')A[i].len=++len;
		else A[i].len=len;
	}
	M=log(len)/log(2)+1; M=(1<<M);
	for(int i=1;i<=m;i++){
		if(A[i].ch=='A')change(A[i].len,(A[i].x+t)%D);
		else printf("%lld\n",t=Query_max(A[i].len-A[i].x+1,A[i].len));
	}
}