Treap求调

RT，找了一份模板照着写，蛋模板没有rank和find，于是自己写了一份，但没过样例QAQ

#include <bits/stdc++.h>
#define maxn 1000010
#define inf 1145141919
using namespace std;
int opt, x;
int a[maxn];
int n, m;
int last = 0;

template<typename T>inline void read(T &ff) {
    T rr = 1;
    ff = 0;
    register char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            rr = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        ff = (ff << 1) + (ff << 3) + (ch ^ 48);
        ch = getchar();
    }
    ff *= rr;
}

struct Treap {//treap模板，有需要可以copy
    int tot, rt;
    struct node {
        int val, ch[2], rd, cnt, sz;
        void Init(int Val) {
            val = Val, rd = rand() % 233;
            sz = cnt = 1;
            ch[1] = ch[0] = 0;
        }
    } tr[maxn];
    void pushup(int nod) {
        tr[nod].sz = tr[tr[nod].ch[0]].sz + tr[tr[nod].ch[1]].sz + tr[nod].cnt;
    }
    void rotate(int &nod, int d) {
        int k = tr[nod].ch[d];
        tr[nod].ch[d] = tr[k].ch[d ^ 1];
        tr[k].ch[d ^ 1] = nod;
        pushup(nod);
        pushup(k);
        nod = k;
    }
    void ins(int &nod, int val) {
        if (!nod) {
            nod = ++ tot;
            tr[nod].Init(val);
        } else {
            tr[nod].sz ++;
            if (tr[nod].val == val) {
                tr[nod].cnt ++;
                return;
            }
            int d = val > tr[nod].val;
            ins(tr[nod].ch[d], val);
            if (tr[nod].rd > tr[tr[nod].ch[d]].rd)
                rotate(nod, d);
        }
    }
    void del(int &nod, int val) {
        if (!nod)
            return;
        if (tr[nod].val == val) {
            if (tr[nod].cnt > 1) {
                tr[nod].cnt --, tr[nod].sz --;
                return;
            }
            int d = tr[tr[nod].ch[0]].rd > tr[tr[nod].ch[1]].rd;
            if (!tr[nod].ch[1] || !tr[nod].ch[0])
                nod = tr[nod].ch[1] + tr[nod].ch[0];
            else
                rotate(nod, d), del(nod, val);
        } else
            tr[nod].sz --, del(tr[nod].ch[tr[nod].val < val], val);
    }
    int _rank(int nod, int val) {
        if (!nod)
            return 0;
        if (tr[nod].val == val)
            return tr[tr[nod].ch[0]].sz + 1;
        if (tr[nod].val < val)
            return tr[tr[nod].ch[0]].sz + tr[nod].cnt + _rank(tr[nod].ch[1], x);
        if (tr[nod].val > val)
            return _rank(tr[nod].ch[0], x);
    }
    int find(int nod, int val) {
        if (!nod)
            return 0;
        if (tr[tr[nod].ch[0]].sz >= val)
            return find(tr[nod].ch[0], val);
        else if (tr[tr[nod].ch[0]].sz + tr[nod].cnt < val)
            return find(tr[nod].ch[1], val - tr[nod].cnt - tr[tr[nod].ch[0]].sz);
        else
            return tr[nod].val; //都等于了，对吧
    }
    int pre(int nod, int val) {
        if (!nod)
            return -inf;
        if (tr[nod].val > val)
            return pre(tr[nod].ch[0], val);
        else
            return max(tr[nod].val, pre(tr[nod].ch[1], val));
    }
    int suc(int nod, int val) {
        if (!nod)
            return inf;
        if (tr[nod].val < val)
            return suc(tr[nod].ch[1], val);
        else
            return min(tr[nod].val, suc(tr[nod].ch[0], val));
    }
    int Get_Min(int nod) {
        if (!nod)
            return inf;
        return min(tr[nod].val, Get_Min(tr[nod].ch[0]));
    }
} tr;

int main() {
    read(n);
    read(m);
    for (register int i = 1; i <= n; i++) {
        read(a[i]);
        tr.ins(tr.rt, a[i]);
    }
    long long ans = 0;
    for (register int i = 1; i <= m; i++) {
        read(opt);
        read(x);
        x ^= last;
        if (opt == 1) {
            tr.ins(tr.rt, x);
        } else if (opt == 2) {
            tr.del(tr.rt, x);
        } else if (opt == 3) {
            last = tr._rank(tr.rt, x);
            ans ^= 1ll * last;
        } else if (opt == 4) {
            last = tr.find(tr.rt, x);
            ans ^= 1ll * last;
        } else if (opt == 5) {
            last = tr.pre(tr.rt, x);
            ans ^= 1ll * last;
        } else if (opt == 6) {
            last = tr.suc(tr.rt, x);
            ans ^= 1ll * last;
        }
    }
    cout << ans;
    return 0;
}