线段树

//单点修改查询
//http://ybt.ssoier.cn:8088/problem_show.php?pid=1549
//https://www.luogu.com.cn/problem/P1198
//用一维数组来存,当作完全二叉树来存
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
long long int m,p,n,last,t;
char op;
struct node
{
    int l,r,v;
}tr[N*4];
void pushup(int u)//更新每个区间的最大值
{
    tr[u].v=max(tr[u*2].v,tr[2*u+1].v);
}
void build(int u,int l,int r)//建立线段树
{
    tr[u]={l,r};
    if(l==r) return;
    int mid=l+r>>1;
    build(2*u,l,mid),build(2*u+1,mid+1,r);//向左建立,向右建立
}
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,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;
}
int 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);
    }
}
int main()
{
    cin>>m>>p;
    build(1,1,m);
    while(m--){
        cin>>op>>t;
        if(op=='Q'){
            last=query(1,n-t+1,n);
            cout<<last<<endl;
        }
        else{
            modify(1,n+1,(last+t)%p);
            n++;
        }
    }
    return 0;
}