分析

• 因为最多存在$2 \times 10^5$个操作，我们开始可以将所有的坑位全部开好，而不是一个一个添加，然后使用一个变量n记录当前有多少位置被占用了。

• 则上面的添加操作可以看成在第n+1个位置的添加一个数。相当于将当前位置的数修改为指定数据。因此，题目中的两个操作可以变为：

（1）修改某个位置的数据；

（2）查询区间$[n-L+1, n]$数的最大值；

• 典型的线段树的操作，可以使用线段树解决。

• 线段树的每个节点一般使用结构体实现，我们必须有存储区间的左右端点l和r，另外还需要存储节点的某种属性（可能是多种），问的属性一般都要存储下来，比如本题问最大值，因此区间[l, r]之间的最大值要存下来；另外还要存储哪些属性呢？

• 其实遵守一个原则即可：根据我们锁存储的属性，能求出父节点的这些属性。

• 我们发现，对于本题而言，存储子节点的最大值足以求出父节点的最大值了，因此存储最大值就足已。

#include <cstdio>
#include <iostream>

using namespace std;

const int N = 200010;

int m, p;  // 操作数, 取模的数
struct Node {
    int l, r;
    int v;  // 区间[l, r]中的最大值
} tr[N * 4];

void pushup(int u) {  // 由子节点的信息，来计算父节点的信息
    tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}

// 节点tr[u]存储区间[l, r]的信息
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);
    // pushup(u);  // 不需要这句话，因为线段树中所有的v都是0
}

// 从节点tr[u]开始查询区间[l, r]的最大值
int query(int u, int l, int r) {

    if (tr[u].l >= l && tr[u].r <= r) return tr[u].v;  // 树中节点，已经被完全包含在[l, r]中了

    int mid = tr[u].l + tr[u].r >> 1;
    int v = 0;
    if (l <= mid) v = query(u << 1, l, r);
    if (r > mid) v = max(v, query(u << 1 | 1, l, r));  // 右区间从mid+1开始

    return v;
}

// 从节点tr[u]开始修改第x个数为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(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);  // 修改子节点，则必须更新父节点
    }
}

int main() {

    int n, last;  // n:插入的数据的个数，last:上次询问的结果
    scanf("%d%d", &m, &p);

    // 创建线段树, 根节点是tr[1]
    build(1, 1, m);

    char op[2];  // 操作码
    int x;  // 操作数
    while (m--) {
        scanf("%s%d", op, &x);
        if (*op == 'Q') {
            // 从根节点1开始查询区间[n-x+1, n]的最大值
            last = query(1, n - x + 1, n);
            printf("%d\n", last);
        } else {
            // 从根节点1开始修改第n+1个数为(x + last) % p
            modify(1, n + 1, (x + last) % p);
            n++;
        }
    }

    return 0;
}