记录编号	457796	评测结果	AAAAAAAAAA
题目名称	[JSOI 2008] 最大数	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	0.800 s
提交时间	2017-10-09 15:58:51	内存使用	6.42 MiB

#include<bits/stdc++.h>
#define ll long long
#define mid ((l+r)>>1)
#define ls o<<1
#define rs o<<1|1
using namespace std;
int m,len;
ll t,d,f[800005];
void change(int l,int r,int o,int x,ll y){
	if(l==r){
		f[o]+=y;f[o]%=d;return ;
	}
	if(mid>=x)change(l,mid,ls,x,y);
	else change(mid+1,r,rs,x,y);
	f[o]=max(f[ls],f[rs]);
}
ll q(int l,int r,int o,int L,int R){
	if(l>=L&&r<=R){
		return f[o];
	}ll k=0;
	if(mid>=L)k=max(k,q(l,mid,ls,L,R));
	if(mid<R)k=max(k,q(mid+1,r,rs,L,R));
	return k;
}
int main()
{
	freopen("bzoj_1012.in","r",stdin);
	freopen("bzoj_1012.out","w",stdout);
	scanf("%d%lld",&m,&d);
	for(int i=1;i<=m;i++){
		char s[10];ll x;scanf("%s%lld",s,&x);
		if(s[0]=='A'){
			change(1,200000,1,++len,x+t);
		}
		else {
			t=q(1,200000,1,len-x+1,len);
			printf("%lld\n",t);
		}
	}
	return 0;
}