由于显然不可能对整个平衡树进行修改，所以我们考虑偷懒，对后来的元素进行等效平移。

记一个偏移量 $\Delta$ 表示平衡树内的元素要加上 $Delta$ 才是真正的数值。

那么本题就很好写了，可以用这题来练一练区间删除。

• 就是把左右端点分别旋上去，再像删除单个元素一样删除区间。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 15;
const int INF = 0x3f3f3f3f;

struct Splay {
    int p, s[2];
    int val;
    int cnt, sz;
} tr[N];

int n, m, rt, tot = 0;
int delta = 0;

void pushup(int u) {
    tr[u].sz = tr[tr[u].s[0]].sz + tr[tr[u].s[1]].sz + tr[u].cnt;
}

void rotate(int x) {
    int y = tr[x].p, z = tr[y].p;
    bool k = (x == tr[y].s[1]);
    tr[z].s[tr[z].s[1] == y] = x, tr[x].p = z;
    tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
    tr[x].s[k ^ 1] = y, tr[y].p = x;
    pushup(y), pushup(x);
}

void splay(int x, int k) {
    while (tr[x].p != k) {
        int y = tr[x].p, z = tr[y].p;
        if (z == k) rotate(x);
        else {
            if ((x == tr[y].s[1]) ^ (y == tr[z].s[1])) rotate(x);
            else rotate(y);
            rotate(x);
        }
    }
    if (!k) rt = x;
}

void insert(int x) {
    int u = rt, fa = 0;
    while (tr[u].val != x && u) {
        fa = u, u = tr[u].s[x > tr[u].val];
    }
    if (u) tr[u].cnt++;
    else {
        u = ++tot;
        tr[u].p = fa;
        if (fa) tr[fa].s[x > tr[fa].val] = u; //可能是根节点所以要特判 fa
        tr[u].cnt = tr[u].sz = 1;
        tr[u].val = x;
    }
    splay(u, 0);    //旋转到根！
}

void build() {
    insert(-INF), insert(INF);
}

int get_val_by_rank(int x) {
    int u = rt;
    if (tr[rt].sz < x) return INF;
    while (15) {
        if (tr[tr[u].s[0]].sz >= x) u = tr[u].s[0];
        else if (tr[tr[u].s[0]].sz + tr[u].cnt >= x) return u;
        else x -= tr[tr[u].s[0]].sz + tr[u].cnt, u = tr[u].s[1];
    }
}

int find(int val) {
    int u = rt, res = 0;
    while (u) {
        if (val <= tr[u].val) {
            res = u;
            u = tr[u].s[0];
        } else {
            u = tr[u].s[1];
        }
    }
    return res;
}

int main() {
    scanf("%d%d", &n, &m);
    build();
    int all = 0;
    while (n--) {
        char opt; int x; scanf(" %c%d", &opt, &x);
        if (opt == 'I') {
            if (x >= m) {
                x -= delta;
                insert(x);
                all++;
            }
        } else if (opt == 'A') delta += x;
        else if (opt == 'S') {
            delta -= x;
            int l = 1, r = find(m - delta);
            splay(l, 0); splay(r, l);
            tr[r].s[0] = 0;
            pushup(r), pushup(l);
        } else {
            if (x > tr[rt].sz - 2) puts("-1");
            else {
                int p = get_val_by_rank(tr[rt].sz - x);
                splay(p, 0);
                printf("%d\n", tr[p].val + delta);
            }
        }
    }
    printf("%d\n", all - (tr[rt].sz - 2));
    return 0;
}