模板稍加变形
利用线段树记录区间最大值先构建空树
插入值时做修改
区间查询 [n-L+1 ,n]
//#pragma GCC optimize(2)
#include<iostream>
#include<queue>
#include<cstring>
#define ios ios::sync_with_stdio(false),cin.tie(NULL)
#define lc k<<1
#define rc k<<1|1
#define int long long
using namespace std;
const int N = 2e5+10;
int m,p;
struct node{
int l,r;
int mx;
}tr[N*4];
int a,cnt;
void pushup(int k){
tr[k].mx = max(tr[lc].mx,tr[rc].mx);
}
void build(int k,int l,int r){
tr[k] = {l,r,0};
if(l == r) return;
int m = l+r>>1;
build(lc,l,m);
build(rc,m+1,r);
pushup(k);
}
void update(int k, int x, int p) {
if (tr[k].l == x && tr[k].r == x) {
tr[k].mx += p;
return;
}
int m = tr[k].l + tr[k].r >> 1;
if (x <= m)update(lc, x, p);
if (x > m)update(rc, x, p);
pushup(k);
}
int query(int k, int l,int r) {
if (tr[k].l >= l && tr[k].r <= r)
return tr[k].mx;
int m = tr[k].l + tr[k].r >> 1;
int ans = 1<<63;
if (l <= m)ans = max(ans, query(lc, l, r));
if (r > m)ans = max(ans, query(rc, l, r));
return ans;
}
signed main(){
ios;
cin>>m>>p;
build(1,1,N);
while(m--){
char op;
int t;
cin>>op>>t;
if(op == 'A')
update(1,++cnt,(t+a)%p);
else{
a = query(1,cnt-t+1,cnt);
cout<<a<<endl;
}
}
return 0;
}