裸线段树就可以了，当然单调栈或者单调队列也可以。
#include<cstdio>
#include<algorithm>
using namespace std;typedef long long ll;
const int maxn=200000+1000;
const ll INF=-1e18;ll node[maxn<<2];
ll Mod;
int tot;void build(int l,int r,int root){node[root]=INF;if(l==r) return ;int mid=(l+r)>>1;build(l,mid,root<<1);build(mid+1,r,root<<1|1);
}
void Update(int l,int r,int ind,int root,ll val){if(l==r) {node[root]=val;return ;}int mid=(l+r)>>1;if(mid>=ind) Update(l,mid,ind,root<<1,val);else Update(mid+1,r,ind,root<<1|1,val); node[root]=max(node[root<<1],node[root<<1|1]);
}ll query(int l,int r,int L,int R,int root){if(l<=L&&r>=R) return node[root];int mid=(L+R)>>1;if(mid<l) return query(l,r,mid+1,R,root<<1|1);else if(mid>=r) return query(l,r,L,mid,root<<1);else return max(query(l,r,L,mid,root<<1),query(l,r,mid+1,R,root<<1|1));
}int main(){int n;scanf("%d%lld",&n,&Mod);ll t=0;build(1,n,1);for(int i=0;i<n;i++){char tmp[10];ll x;scanf("%s%lld",tmp,&x);if(tmp[0]=='A'){x=(x+t)%Mod;tot++;Update(1,n,tot,1,x);}else{printf("%lld\n",t=query(tot-x+1,tot,1,n,1));}}
}