Splay 92分求调

TLE on #5, 6

如之奈何？

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2000010, INF = (1 << 30) + 1;

struct Node {
    int ch[2];
    int size;
    int p, v;
    int cnt;
}tr[N];

int root, idx;

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

void rotate(int x) {
    int y = tr[x].p;
    int z = tr[y].p;
    int k = tr[y].ch[1] == x;

    tr[z].ch[tr[z].ch[1] == y] = x, tr[x].p = z;
    tr[y].ch[k] = tr[x].ch[k ^ 1], tr[tr[x].ch[k ^ 1]].p = y;
    tr[x].ch[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;
        int z = tr[y].p;

        if (z != k) {
            if ((tr[z].ch[1] == y) ^ (tr[y].ch[1] == x)) rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
    if (!k) root = x;
}

void find(int x) {
    int u = root;
    while (tr[u].ch[x > tr[u].v] && tr[u].v != x) {
        u = tr[u].ch[x > tr[u].v];
    }
    splay(u, 0);
}

int get_pre(int x) {
    find(x);
    if (tr[root].v < x) return root;
    int u = tr[root].ch[0];
    while (tr[u].ch[1]) u = tr[u].ch[1];
    return u;
}

int get_suc(int x) {
    find(x);
    if (tr[root].v > x) return root;
    int u = tr[root].ch[1];
    while (tr[u].ch[0]) u = tr[u].ch[0];
    return u;
}

void insert(int x) {
    int p = 0, u = root;
    while (u && tr[u].v != x)
        p = u, u = tr[u].ch[x > tr[u].v];
    if (u) tr[u].cnt++;
    else {
        u = ++idx;
        if (p) tr[p].ch[x > tr[p].v] = u;
        tr[u].p = p;
        tr[u].size = tr[u].cnt = 1;
        tr[u].v = x;
    }
    splay(u, 0);
}

void del(int x) {
    int pre = get_pre(x);
    int suc = get_suc(x);
    splay(pre, 0);
    splay(suc, pre);
    int del_v = tr[suc].ch[0];
    if (tr[del_v].cnt > 1) tr[del_v].cnt--, splay(del_v, 0);
    else tr[suc].ch[0] = 0, splay(suc, 0);
}

int get_rank_by_key(int x) {
    find(x);
    if (tr[root].v == x) return tr[tr[root].ch[0]].size;
    int p = get_pre(x);
    find(tr[p].v);
    return tr[tr[root].ch[0]].size + 1;
}

int get_key_by_rank(int k) {
    int u = root;
    while (true) {
        if (k <= tr[tr[u].ch[0]].size) u = tr[u].ch[0];
        else if (k <= tr[tr[u].ch[0]].size + tr[u].cnt) break;
        else k -= tr[tr[u].ch[0]].size + tr[u].cnt, u = tr[u].ch[1];
    }
    splay(u, 0);
    return tr[u].v;
}

int n, m;

int main() {
    freopen("2.in", "r", stdin);
    freopen("2.out", "w", stdout);

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    insert(-INF);
    insert(INF);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        insert(x);
    }

    int last = 0;
    int opt, x;
    int res = 0;

    for (int i = 1; i <= m; i++) {
        cin >> opt >> x;
        x ^= last;
        if (opt == 1) insert(x);
        else if (opt == 2) del(x);
        else if (opt == 3) insert(x), res ^= (last = get_rank_by_key(x)), del(x), cout << opt << ' ' << last << '\n';
        else if (opt == 4) res ^= (last = get_key_by_rank(x + 1)), cout << opt << ' ' << last << '\n';
        else if (opt == 5) res ^= (last = tr[get_pre(x)].v), cout << opt << ' ' << last << '\n';
        else res ^= (last = tr[get_suc(x)].v), cout << opt << ' ' << last << '\n';
    }

    cout << res << '\n';
    return 0;
}