记录编号	240185	评测结果	AAAAAAAAAA
题目名称	[JSOI 2008] 最大数	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.297 s
提交时间	2016-03-22 07:20:12	内存使用	3.34 MiB

#include<cstdio>
#include<cctype>
const int maxn=200005;
unsigned long long s[maxn],index[maxn];
int tail=0;
unsigned long long bi_search(int x){
    int l=0,r=tail-1;
    while(l<=r){
        int mid=(l+r)>>1;
        if(index[mid]<=x)l=mid+1;
        else r=mid-1;
    }
    return s[l];
}
char read_ch(){
	char ch;
	while(ch=getchar(),!isalpha(ch));
	return ch;
}
void add(unsigned long long x,int i){
    while(tail&&s[tail-1]<=x)tail--;
    s[tail]=x;index[tail++]=i;
}
int main(){
  freopen("bzoj_1012.in","r",stdin);
	freopen("bzoj_1012.out","w",stdout);
    unsigned long long m,d,t=0;int k=0;
	scanf("%lld %lld",&m,&d);
	unsigned long long a;
	while(m--){
		char ch=read_ch();scanf("%llu",&a);
		if(ch=='A'){
		    k++;
		  //  printf("t%%d+a%%d==%llu",t%d+a%d);
			add((t%d+a%d)%d,k);
		}else{
			printf("%llu\n",t=bi_search(k-a));
		}
	}
	fclose(stdin);fclose(stdout);
	return 0;
}