记录编号	462133	评测结果	AAAAAAAAAA
题目名称	[JSOI 2008] 最大数	最终得分	100
用户昵称	~玖湫~	是否通过	通过
代码语言	C++	运行时间	0.420 s
提交时间	2017-10-21 11:10:49	内存使用	3.36 MiB

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
#define int long long
const int M=200010;
int n,mod,tail,last,num;
int deq[M],id[M];
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
	return x*f;
} 
inline void add(int val,int i){
	while(tail&&deq[tail]<=val) --tail;
	deq[++tail]=val;id[tail]=i;
}
inline int erfen(int x){
	int l=1,r=tail,ans;
	while(l<=r){
		int mid=l+r>>1;
		if(id[mid]>=x) {ans=mid;r=mid-1;}
		else l=mid+1;
	}return deq[ans];
}
signed main(){
	freopen("bzoj_1012.in","r",stdin);
	freopen("bzoj_1012.out","w",stdout);
	n=read();mod=read();char s[2];int xx;
	for(int T=1;T<=n;++T){
		scanf("%s",s);xx=read();
		if(s[0]=='A'){
			xx=(xx%mod+last)%mod;
			add(xx,++num);
			continue;
		}printf("%lld\n",last=erfen(num-xx+1));
	}return 0;
}
/*
4 100
A 96
Q 1
A 97
Q 1
*/