普通平衡树加强版，带旋 Treap，不知道哪里写挂了

#include<bits/stl_algobase.h>
#include<ctype.h>
#include<cstdio>
#include<random>
using namespace std;
const int N = 1.1e6 + 10;
const int INF = 0x3f3f3f3f;

#define endl '\n'
namespace io {
    struct istream {
        char ch;
        inline istream &operator>>(int &x) {
            while(!isdigit(ch = getchar_unlocked()));
            x = ch - '0';
            while(isdigit(ch = getchar_unlocked())) x = x * 10 + ch - '0';
            return *this;
        }
    } cin;
    struct ostream {
        char buf[60], top;
        inline ostream() : top(0) {}
        inline ostream &operator<<(int x) {
            do buf[++top] = x % 10 + '0', x /= 10; while(x);
            while(top) putchar_unlocked(buf[top--]);
            return *this;
        }
        inline ostream &operator<<(char c) {
            putchar_unlocked(c);
            return *this;
        }
        inline ostream &operator<<(const char s[]) {
            for(int i = 0; s[i]; i++) putchar_unlocked(s[i]);
            return *this;
        }
    } cout;
}

using io::cin;
using io::cout;

namespace Treap {
    mt19937 rng((random_device){}());
    int val[N], pri[N], sz[N], chd[N][2], nn, rt;
    inline int addNode(int v) {
        val[++nn] = v;
        pri[nn] = rng();
        sz[nn] = 1; 
        return nn;
    }
    inline void push_up(int p) {
        sz[p] = sz[chd[p][0]] + sz[chd[p][1]] + 1;
    }
    inline void rotate(int &x, int d) {
        int y = chd[x][d], z = chd[y][d ^ 1];
        chd[x][d] = z;
        chd[y][d ^ 1] = x;
        push_up(x);
        push_up(y);
        x = y;
    }
    void insert(int &p, int v) {
        if(!p) { p = addNode(v); return; }
        int d = v > val[p];
        insert(chd[p][d], v);
        if(pri[chd[p][d]] < pri[p]) rotate(p, d);
        else push_up(p);
    }
    void erase(int &p, int v) {
        if(!p) throw;
        if(val[p] == v) {
            if(!chd[p][0]) { p = chd[p][1]; return; }
            if(!chd[p][1]) { p = chd[p][0]; return; }
            if(pri[chd[p][0]] < pri[chd[p][1]]) { rotate(p, 0); erase(chd[p][1], v); }
            else { rotate(p, 1); erase(chd[p][0], v); }
        } else {
            erase(chd[p][v > val[p]], v);
        }
        push_up(p);
    }
    int queryRank(int &p, int v) {
        if(!p) return 0;
        if(val[p] < v) return sz[chd[p][0]] + 1 + queryRank(chd[p][1], v);
        else return queryRank(chd[p][0], v);
    }
    int queryKth(int &p, int k) {
        if(k > sz[p]) throw;
        if(k == sz[chd[p][0]] + 1) return val[p];
        if(k <= sz[chd[p][0]]) return queryKth(chd[p][0], k);
        return queryKth(chd[p][1], k - sz[chd[p][0]] - 1);
    }
    int queryPre(int &p, int v) {
        if(!p) return -1;
        if(val[p] < v) return max(val[p], queryPre(chd[p][1], v));
        return queryPre(chd[p][0], v);
    }
    int querySuc(int &p, int v) {
        if(!p) return INF;
        if(val[p] > v) return min(val[p], querySuc(chd[p][0], v));
        return querySuc(chd[p][1], v);
    }
    inline void insert(int v) { insert(rt, v); }
    inline void erase(int v) { erase(rt, v); }
    inline int queryRank(int v) { return queryRank(rt, v); }
    inline int queryKth(int k) { return queryKth(rt, k); }
    inline int queryPre(int v) { return queryPre(rt, v); }
    inline int querySuc(int v) { return querySuc(rt, v); }
}

using namespace Treap;

int n, m;
int lastans, ans;

inline void addAns(int res) {
    lastans = res;
    ans ^= res;
}

int main() {

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

    while(m--) {
        int op, x;
        cin >> op >> x;
        x ^= lastans;
        if(op == 1) Treap::insert(x);
        else if(op == 2) Treap::erase(x);
        else if(op == 3) addAns(Treap::queryRank(x) + 1);
        else if(op == 4) addAns(Treap::queryKth(x));
        else if(op == 5) addAns(Treap::queryPre(x));
        else if(op == 6) addAns(Treap::querySuc(x));
    }

    cout << ans << '\n';

    return 0;
}