线段树裸题！动态RMQ。
这道题的操作是直接在序列末尾添加数值，所以连(push_{down})，以及建树什么的都不用了。。
这真是写过的最简短的一道(seg_{tree})了2333
（似乎有很多其他做法，不过没有研究qwq（因为太菜））
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
#define ll long long
#define mod d
#define MAXN 200233
#define inf -5223372036854775808
#define leftson cur<<1
#define rightson cur<<1|1
#define mid ((l+r)>>1)
#define push_up ans[cur]=llmax(ans[leftson],ans[rightson])%mod
ll m,d;
int tot=0;
ll llmax(ll x,ll y)
{
return x>y?x:y;
}
ll ans[MAXN<<2]={};
inline void change(int adc,int cur,int l,int r,int del)
{
if (l==r)
{
ans[cur]=del;
return;
}
if (adc<=mid) change(adc,leftson,l,mid,del);
if (adc>mid) change(adc,rightson,mid+1,r,del);
push_up;
}
inline ll query(int adl,int adr,int cur,int l,int r)
{
if (adl<=l&&r<=adr)
{
return ans[cur];
}
ll x=inf,y=inf;
if (adl<=mid) x=query(adl,adr,leftson,l,mid);
if (adr>mid) y=query(adl,adr,rightson,mid+1,r);
return llmax(x,y);
}
int main()
{
scanf("%lld%lld",&m,&d);
char q;
ll a,b=0;
for (int i=1;i<=m;i++)
{
cin>>q;
scanf("%lld",&a);
if (q=='A')
{
change(++tot,1,1,m,(a+b)%mod);
continue;
}
if (a==0) b=0;
else b=query(tot-a+1,tot,1,1,m);
printf("%lld
",b);
}
return 0;
}