https://www.luogu.org/problemnew/show/P1198
要问区间最大值，肯定是要用线段树的，不能用树状数组。（因为没有逆元？但是题目求的是最后一段，可以改成类似前缀和啊。不行！插入新元素之后更新的复杂度太高了！）
所以我们就弄一个初始元素是负数的最大值线段树，每次插入就是把末尾的元素 $update$ ，查询就是查询末尾的区间最大值，这样每次修改/查询的复杂度是 $O(nlogn)$ 的，非常给力。
所以说我又要到哪里抄一个线段树模板。
注意这个线段树是从1开始计数的。
#include<bits/stdc++.h>
using namespace std;
#define ll long long const int MAXM=;
int a[MAXM+],st[(MAXM<<)+]; void build(int o,int l,int r){
if(l==r) st[o]=a[l];
else{
int m=l+((r-l)>>);
build(o<<,l,m);
build(o<<|,m+,r);
st[o]=max(st[o<<],st[o<<|]);
}
} void update(int o,int l,int r,int id,int v){
if(l==r) st[o]=v;
else{
int m=l+((r-l)>>);
if(id<=m) update(o<<,l,m,id,v);
else update(o<<|,m+,r,id,v);
st[o]=max(st[o<<],st[o<<|]);
}
} int query(int o,int l,int r,int a,int b){
if(r<a||l>b) return -;
if(a<=l&&r<=b) return st[o];
int m=l+((r-l)>>);
int p1=query(o<<,l,m,a,b),p2=query(o<<|,m+,r,a,b);
return max(p1,p2);
} int M;
ll D;
int t; char s[];
int ins; int cntA=; int main(){
t=;
scanf("%d%lld",&M,&D);
for(int i=;i<=M;i++){
a[i]=-;
}
build(,,M);
for(int i=;i<=M;i++){
scanf("%s%d",s,&ins);
if(s[]=='Q'){
t=query(,,M,cntA-ins+,cntA);
printf("%d\n",t);
}
else{
update(,,M,cntA+,((1ll*ins)+t)%D);
cntA++;
}
}
}