FHQ Treap 求调（悬3关）

获得了 92pts RE 的好成绩。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1000010;
int rt, sz, v[N], w[N], s[N], ch[N][2];
void update(int k) { s[k] = s[ch[k][0]] + s[ch[k][1]] + 1; }
void split(int now, int k, int &x, int &y)
{
    if (!now) x = y = 0;
    else
    {
        if (v[now] <= k) x = now, split(ch[now][1], k, ch[now][1], y);
        else y = now, split(ch[now][0], k, x, ch[now][0]);
        update(now);
    }
}
void split_kth(int now, int k, int &x, int &y)
{
    if (!now) x = y = 0;
    else
    {
        if (k <= s[ch[now][0]]) y = now, split_kth(ch[now][0], k, x, ch[now][0]);
        else x = now, split_kth(ch[now][1], k - s[ch[now][0]] - 1, ch[now][1], y);
        update(now);
    }
}
int merge(int x, int y)
{
    if (!x || !y) return x + y;
    if (w[x] < w[y]) return ch[x][1] = merge(ch[x][1], y), update(x), x;
    return ch[y][0] = merge(x, ch[y][0]), update(y), y;
}
int new_node(int _v)
{
    v[++sz] = _v, w[sz] = rand(), s[sz] = 1, ch[sz][0] = ch[sz][1] = 0;
    return sz;
}
void insert(int &rt, int v)
{
    int x, y; split(rt, v, x, y);
    rt = merge(merge(x, new_node(v)), y);
}
void del(int &rt, int v)
{
    int x, y, z; split(rt, v, x, z), split(x, v - 1, x, y);
    y = merge(ch[y][0], ch[y][1]), rt = merge(merge(x, y), z);
}
int query_rank(int &rt, int v)
{
    int x, y; split(rt, v - 1, x, y);
    int ret = s[x] + 1; rt = merge(x, y);
    return ret;
}
int kth(int &rt, int k)
{
    int x, y, z; split_kth(rt, k - 1, x, y);
    split_kth(y, 1, y, z), rt = merge(merge(x, y), z);
    return y;
}
int query_pre(int &rt, int v)
{
    int x, y, z; split(rt, v - 1, x, y);
    for (z = x; ch[z][1]; z = ch[z][1]);
    rt = merge(x, y);
    return z;
}
int query_post(int &rt, int v)
{
    int x, y, z; split(rt, v, x, y);
    for (z = y; ch[z][0]; z = ch[z][0]);
    rt = merge(x, y);
    return z;
}

int main()
{
    srand(time(NULL));
    int n, m, lst = 0; ll ret = 0; scanf("%d%d", &n, &m);
    for (int i = 1, k; i <= n; i++) scanf("%d", &k), insert(rt, k);
    while (m--)
    {
        int op, x; scanf("%d%d", &op, &x), x ^= lst;
        if (op == 1) insert(rt, x);
        else if (op == 2) del(rt, x);
        else if (op == 3) lst = query_rank(rt, x), ret ^= lst;
        else if (op == 4) lst = v[kth(rt, x)], ret ^= lst;
        else if (op == 5) lst = v[query_pre(rt, x)], ret ^= lst;
        else lst = v[query_post(rt, x)], ret ^= lst;
    } printf("%lld\n", ret);
    return 0;
}