莫欺少年穷，修魔之旅在这开始—>算法提高课题解

思路：

1. 先建立线段树
2. 添加操作：直接修改 ++n 位置的数（回溯时不要忘了更新最大值）
3. 查询操作则有以下三种情况：
4. （1）若该树区间完全包含在被查询的区间内，则直接返回该树区间的最大值
5. （2）若[tr[u].l, mid] 与 [l, r]有交集，则递归左边
6. （3）若[l, r] 与 [mid + 1, tr[u].r]有交集，则递归右边

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 200010;

int n,m,p,last;
struct Node
{
    int l,r；
    int v; //最大值
}tr[N*4]; //最大空间开 4 倍

//由子节点求父节点的最大值
void pushup(int u)
{
    tr[u].v=max(tr[u<<1].v,tr[u<<1|1].v);
}

//提前把线段树开出来
void build(int u,int l,int r)
{
    tr[u]={l,r};
    if(l==r) return;

    int mid=l+r>>1;
    build(u<<1,l,mid),build(u<<1|1,mid+1,r);
}

//以 u 为根节点开始查询区间[l, r]中的最大值
int query(int u,int l,int r)
{
    //该区间完全在[l, 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;

    // [tr[u].l, mid] 与 [l, r]有交集
    if(l<=mid) v=query(u<<1,l,r);

    // [l, r] 与 [mid + 1, tr[u].r]有交集
    if(mid<r) v=max(v,query(u<<1|1,l,r));

    return v;
}

//以 u 为根节点开始修改第 x 个数
void modify(int u,int x,int v)
{
    if(tr[u].l==tr[u].r&&tr[u].l==x) tr[u].v=v;
    else 
    {
        int mid=tr[u].l+tr[u].r>>1;
        if(x<=mid) modify(u<<1,x,v);
        else modify(u<<1|1,x,v);

        //回溯更新区间最大值
        pushup(u);
    }
}

int main()
{
    cin>>m>>p;

    //建立线段树
    build(1,1,m);

    char op;
    int x;
    while(m--)
    {
        cin>>op>>x;

        //询问操作
        if(op=='Q')
        {
            last=query(1,n-x+1,n);
            cout<<last<<endl;
        }
        //添加操作
        else modify(1,++n,((LL)last+x)%p);
    }

    return 0;
}