难度： 绿

算法： 线段树，或其它数据结构

单点修改（把在最后插一个数的操作视为将最后一位从 $0$ 改为 $x$），区间查询最大值，直接线段树。

没什么好说的，自己看代码吧。

#include<bits/stdc++.h>
using namespace std;
int q,x,n,a=0,p;
int s[840000],l[840000],r[840000];
char c;
void build(int le,int ri,int id){
	l[id]=le,r[id]=ri;
	if(le==ri) return ;
	build(le,(le+ri)/2,2*id);
	build((le+ri)/2+1,ri,2*id+1);
}
void upd(int pos,int num,int id){
	int nl=l[id],nr=r[id],mid=(nl+nr)/2;
	if(nl==pos&&nr==pos){
		s[id]=max(s[id],num);
		return;
	} 
	if(pos<=mid) upd(pos,num,id*2);
	if(pos>mid) upd(pos,num,id*2+1);
	s[id]=max(s[id*2],s[id*2+1]);
}
int que(int le,int ri,int id){
	int nl=l[id],nr=r[id],mid=(nl+nr)/2;
	if(le<=nl&&nr<=ri) return s[id];
	int res=0;
	if(le<=mid) res=max(res,que(le,ri,id*2));
	if(ri>mid) res=max(res,que(le,ri,id*2+1));
	return res;
}
int main(){
	ios::sync_with_stdio(0);
	cin>>q>>p;
	build(1,q,1);
	while(q--){
		cin>>c>>x;
		if(c=='A'){
			x=((long long)x+a)%p;
			upd(++n,x,1);
		}
		else{
			a=que(n-x+1,n,1);
			printf("%d\n",a);
		}
	}
}