30求助

#include <stdio.h>
#include <stdlib.h>
const int N = (int)1e6 + 1e5 + 5, inf = 0x3f3f3f3f;
int n, m, ch[N][2], val[N], dt[N], sz[N], cnt[N], tot, rt;
inline void Read(int &x) {
    x = 0; int w = 1; char c = getchar();
    for (; c < '0' || c > '9'; c = getchar())
        if (c == '-') w = -1;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = (x << 3) + (x << 1) + (c ^ 48);
    x *= w;
}
inline int New(int u) {
    val[++tot] = u; dt[tot] = rand();
    sz[tot] = cnt[tot] = 1; return tot;
}
inline void Pushup(int id) {
    sz[id] = sz[ch[id][0]] + sz[ch[id][1]] + cnt[id];
}
inline void Build() {
    rt = New(-inf);
    ch[rt][1] = New(inf);
    Pushup(rt);
}
inline void Rotate(int &id, int dir) {
    int temp = ch[id][dir ^ 1];
    ch[id][dir ^ 1] = ch[temp][dir];
    ch[temp][dir] = id;
    id = temp;
    Pushup(ch[id][dir]);
    Pushup(id);
}
inline void Insert(int &id, int u) {
    if (id == 0) {id = New(u); return;}
    if (u == val[id]) ++cnt[id];
    else {
        int dir = !(u < val[id]);
        Insert(ch[id][dir], u);
        if (dt[id] < dt[ch[id][dir]]) Rotate(id, dir ^ 1);
    }
    Pushup(id);
}
inline void Remove(int & id, int u) {
    if (id == 0) return;
    if (u == val[id]) {
        if (cnt[id] > 1) {--cnt[id]; Pushup(id); return;}
        if (ch[id][0] || ch[id][1]) {
            if (!ch[id][1] || dt[ch[id][0]] > dt[ch[id][1]]) {Rotate(id, 1); Remove(ch[id][1], u);}
            else {Rotate(id, 0); Remove(ch[id][0], u);}
            Pushup(id);
        }
        else id = 0;
        return;;
    }
    if (u < val[id]) Remove(ch[id][0], u);
    else Remove(ch[id][1], u);
    Pushup(id);
}
inline int query_rk(int id, int u) {
    if (id == 0) return 0;
    if (u == val[id]) return sz[ch[id][0]] + 1;
    else
        if (u < val[id]) return query_rk(ch[id][0], u);
        else return sz[ch[id][0]] + query_rk(ch[id][1], u) + cnt[id];
}
inline int query_val(int id, int rk) {
    if (id == 0) return inf;
    if (rk <= sz[ch[id][0]]) return query_val(ch[id][0], rk);
    else
        if (rk <= sz[ch[id][0]] + cnt[id]) return val[id];
        else return query_val(ch[id][1], rk - sz[ch[id][0]] - cnt[id]);
}
inline int query_pre(int u) {
    int id = rt, pre;
    while (id) {
        if (val[id] < u) {pre = val[id]; id = ch[id][1];}
        else id = ch[id][0];
    }
    return pre;
}
inline int query_nxt(int u) {
    int id = rt, nxt;
    while (id) {
        if (val[id] > u) {nxt = val[id]; id = ch[id][0];}
        else id = ch[id][1];
    }
    return nxt;
}
int main(void) {
    Build(); Read(n); Read(m);
    for (int x; n--; ) {
        scanf("%d", &x);
        Insert(rt, x);
    }
    int tot = 0;
    for (int opt, x, pre = 0; m--; ) {
        Read(opt); Read(x); x ^= pre;
        switch (opt) {
            case 1: Insert(rt, x); break;
            case 2: Remove(rt, x); break;
            case 3: tot ^= (pre = query_rk(rt, x) - 1); break;
            case 4: tot ^= (pre = query_val(rt, x + 1)); break;
            case 5: tot ^= (pre = query_pre(x)); break;
            default: tot ^= (pre = query_nxt(x));
        }
    }
    printf("%d\n", tot);
    return 0;
}

WA 30分