Splay 求调（96 pts TLE on #11）

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 1e5 + 5;
int ch[N][2], fa[N], v[N], cnt[N], siz[N], num, root, n, m, ans;
inline void rotate(int x) {
    int y = fa[x], z = fa[y], k = (ch[y][1] == x);
    ch[z][ch[z][1] == y] = x;
    fa[x] = z;
    ch[y][k] = ch[x][k ^ 1];
    fa[ch[x][k ^ 1]] = y;
    ch[x][k ^ 1] = y;
    fa[y] = x;
    siz[y] = siz[ch[y][0]] + siz[ch[y][1]] + cnt[y];
    siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + cnt[x];
}
inline void splay(int x, int pos) {
    while (fa[x] != pos) {
        int y = fa[x];
        if (fa[y] != pos) (ch[fa[x]][1] == x) == (ch[fa[y]][1] == y) ? rotate(y) : rotate(x);
        rotate(x);
    }
    if (!pos) root = x;
}
inline void insert(int x) {
    int cur = root, p = 0;
    while (cur && v[cur] != x) p = cur, cur = ch[cur][x > v[cur]];
    if (cur) ++cnt[cur];
    else {
        cur = ++num;
        if (p) ch[p][x > v[p]] = cur;
        ch[cur][0] = ch[cur][1] = 0, fa[cur] = p, v[cur] = x, cnt[cur] = 1, siz[cur] = 1;
    }
    splay(cur, 0);
}
inline void find(int x) {
    int cur = root;
    while (ch[cur][x > v[cur]] && x - v[cur]) cur = ch[cur][x > v[cur]];
    splay(cur, 0);
}
inline int kth(int k) {
    int cur = root;
    if (!k) return 0;
    while (true) {
        if (ch[cur][0] && k <= siz[ch[cur][0]]) cur = ch[cur][0];
        else if (k > siz[ch[cur][0]] + cnt[cur]) k -= siz[ch[cur][0]] + cnt[cur], cur = ch[cur][1];
        else return cur;
    }
}
inline int pre(int x) {
    find(x);
    if (v[root] < x) return root;
    int cur(ch[root][0]);
    while (ch[cur][1]) cur = ch[cur][1];
    return cur;
}
inline int suc(int x) {
    find(x);
    if (v[root] > x) return root;
    int cur = ch[root][1];
    while (ch[cur][0]) cur = ch[cur][0];
    return cur;
}
inline void remove(int x) {
    int lst = pre(x), nxt = suc(x);
    splay(lst, 0);
    splay(nxt, lst);
    if (cnt[ch[nxt][0]] > 1) --cnt[ch[nxt][0]], splay(ch[nxt][0], 0);
    else ch[nxt][0] = 0;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> m;
    insert(INT_MIN);
    insert(INT_MAX);
    for (int i = 1, x; i <= n; ++i) {
        cin >> x;
        insert(x);
    }
    for (int i = 1, op, x, lst = 0; i <= m; ++i) {
        cin >> op >> x;
        x ^= lst;
        if (op == 1) insert(x);
        else if (op == 2) remove(x);
        else if (op == 3) insert(x), find(x), lst = siz[ch[root][0]], ans ^= lst, remove(x);
        else if (op == 4) lst = v[kth(x + 1)], ans ^= lst;
        else if (op == 5) insert(x), lst = v[pre(x)], ans ^= lst, remove(x);
        else insert(x), lst = v[suc(x)], ans ^= lst, remove(x);
    }
    cout << ans;
    return 0;
}