56分求助

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

using namespace std;
#define int long long
const int N = 1e5 + 5, INF = 1e18;

int n, q, last, ans;
struct node {
    int l, r;
    int key, val;
    int cnt, size;   
} tr[N * 100];

int root, idx;

void pushup(int p) {
    tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + tr[p].cnt;
}

int get_node(int key) {
    tr[++idx].key = key;
    tr[idx].val = rand();
    tr[idx].cnt = tr[idx].size = 1;
    return idx;
}

void zig(int &p) {
    int q = tr[p].l;
    tr[p].l = tr[q].r, tr[q].r = p, p = q;
    pushup(tr[p].r), pushup(p);
}

void zag(int &p) {
    int q = tr[p].r;
    tr[p].r = tr[q].l, tr[q].l = p, p = q;
    pushup(tr[p].l), pushup(p);
}

void build() {
    get_node(-INF), get_node(INF);
    root = 1, tr[1].r = 2;
    pushup(root);
    if(tr[1].val < tr[2].val) {
        zag(root);
    }
}

void insert(int &p, int key) {
    if(!p) {
        p = get_node(key);
    } else if(tr[p].key == key) {
        tr[p].cnt++;
    } else if(tr[p].key > key) {
        insert(tr[p].l, key);
        if(tr[tr[p].l].val > tr[p].val) {
            zig(p);
        }
    } else {
        insert(tr[p].r, key);
        if(tr[tr[p].r].val > tr[p].val) {
            zag(p);
        }
    }
    pushup(p);
}

void remove(int &p, int key) {
    if(!p) {
        return;
    }
    if(tr[p].key == key) {
        if(tr[p].cnt > 1) {
            tr[p].cnt--;
        } else if(tr[p].l || tr[p].r){
            if(tr[p].r == 0 || tr[tr[p].l].val > tr[tr[p].r].val) {
                zig(p);
                remove(tr[p].r, key);
            } else {
                zag(p);
                remove(tr[p].l, key);
            }
        } else {
            p = 0;
        }
    } else if(tr[p].key > key) {
        remove(tr[p].l, key);
    } else {
        remove(tr[p].r, key);
    }
    pushup(p);
}

int get_rank_by_key(int p, int key) {
    if(!p) {
        return 0;
    }
    if(tr[p].key == key) {
        return tr[tr[p].l].size + 1;
    }
    if(tr[p].key > key) {
        return get_rank_by_key(tr[p].l, key);
    }
    return tr[tr[p].l].size + tr[p].cnt + get_rank_by_key(tr[p].r, key);
}

int get_key_by_rank(int p, int rank) {
    if(!p) {
        return INF;
    }
    if(tr[tr[p].l].size >= rank) {
        return get_key_by_rank(tr[p].l, rank);
    }
    if(tr[tr[p].l].size + tr[p].cnt >= rank) {
        return tr[p].key;
    }
    return get_key_by_rank(tr[p].r, rank - tr[tr[p].l].size - tr[p].cnt);
}

int get_prev(int p, int key) {
    if(!p) {
        return -INF;
    }
    if(tr[p].key >= key) {
        return get_prev(tr[p].l, key);
    }
    return max(tr[p].key, get_prev(tr[p].r, key));
}

int get_next(int p, int key) {
    if(!p) {
        return INF;
    }
    if(tr[p].key <= key) {
        return get_next(tr[p].r, key);
    }
    return min(tr[p].key, get_next(tr[p].l, key));
}

signed main() {
    build();
    srand(time(0));
    scanf("%lld%lld", &n, &q);
    for(int i = 1, a; i <= n; i++) {
        scanf("%lld", &a);
        insert(root, a);
    }
    while(q--) {
        int op, x;
        scanf("%lld%lld", &op, &x);
        x ^= last;
        if (op == 1) {
            insert(root, x);
        } else if (op == 2) {
            remove(root, x);
        } else if (op == 3) {
            last = get_rank_by_key(root, x);
        } else if (op == 4) {
            last = get_key_by_rank(root, x + 1);
        } else if (op == 5) {
            last = get_prev(root, x);
        } else {
            last = get_next(root, x);
        }
        if(op != 1 && op != 2) ans ^= last;
    }
    printf("%lld", ans);
    return 0;
}

快调炸了