1275 最大数

#include<bits/stdc++.h>
#define fi first
#define sc second
using namespace std;
typedef pair<int,int> PII;
typedef long long LL;

const int N=200010;
struct node
{
    int l,r;
    int v;
}tr[4*N];

int m,p;

void build(int u,int l,int r)
{
    tr[u]={l,r,0};
    if(l==r) return;
    int mid=l+r>>1;
    build(2*u,l,mid);
    build(2*u+1,mid+1,r);
}

void pushup(int u)
{
    tr[u].v=max(tr[u*2].v,tr[u*2+1].v);
}

int query(int u,int l,int r)
{
    if(tr[u].l>=l && tr[u].r<=r) return tr[u].v;
    int mid=tr[u].l+tr[u].r>>1;
    int v=0;
    if(l<=mid) v=query(2*u,l,r);
    if(r>mid) v=max(v,query(2*u+1,l,r));
    return v;
}

void modify(int u,int x,int v)
{
    if(tr[u].l==x && tr[u].r==x) tr[u].v=v;
    else 
    {
        int mid=tr[u].l+tr[u].r>>1;
        if(x<=mid) modify(2*u,x,v);
        else modify(2*u+1,x,v);
        pushup(u);
    }
}

void solve()
{
    int n=0,last=0;
    cin>>m>>p;

    build(1,1,m);

    string op;
    int t;
    for(int i=1;i<=m;i++)
    {

        cin>>op>>t;
        if(op=="Q")
        {
            last=query(1,n-t+1,n);
            cout<<last<<endl;
        }
        else 
        {
            n++;
            modify(1,n,((LL)t+last)%p);  
        }
    }
}

int main()
{
    solve();
    return 0;
}