开一个单调队列，下标递增，值递减。
然后在上面二分最大数。
如果加上并查集可以做到接近线性。
还有一种是插入一个数然后，从后向前更新ST表。
#include<cstdio>
#include<iostream>
#define R register int
using namespace std;
inline int g() {
R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;
do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret*fix;
} const int N=;
int n,M,cnt,top,t;
int a[N],q[N];
signed main() {
n=g(),M=g(); for(R i=,x;i<=n;++i) { register char s[];
scanf("%s",s),x=g(); if(s[]=='A') {
a[++cnt]=(x+t)%M;
while(top&&a[q[top]]<a[cnt]) --top;
q[++top]=cnt;
} else if(s[]=='Q') printf("%d\n",t=a[*lower_bound(q+,q+top+,cnt-x+)]);
}
}
ST表：
#include<cstdio>
#include<iostream>
#include<cmath>
#define ll long long
#define R register ll
using namespace std;
namespace jack {
#define db double
int n,m; ll t,d,ans,a[],f[][]; bool flg;
inline int max(int a,int b) {return a>b?a:b;}
inline void change(int u) {f[u][]=a[u]; for(R i=;u-(<<i)>=;i++) f[u][i]=max(f[u][i-],f[u-(<<(i-))][i-]);}//反向ST表
inline ll find(int a,int b) {db t=log2(b-a+); R k=t; return max(f[b][k],f[a+(<<k)-][k]);}
inline ll g() {
R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;
do ret=(ret<<)+(ret<<)+(ch^); while(isdigit(ch=getchar())); return fix*ret;
}
inline void main() {
m=g(),d=g();
for(R i=;i<=m;i++) {
register char ch;
while(!isalpha(ch=getchar()));
if(ch=='A') {R x=g();a[++n]=(x+t)%d,change(n);}
else {
R l=g(); if(l==) {printf("%lld\n",a[n]),t=a[n];continue;}
ans=find(n-l+,n);
printf("%lld\n",ans); t=ans;
}
}
}
}
signed main() {jack::main();}
2019.07.03