测试

enum {
Maxn = 1000005
};

struct FHQTreap {
int lson[Maxn], rson[Maxn], data[Maxn];
int rnd[Maxn], sze[Maxn], root, tot, seed;
FHQTreap(void) {
Ms(lson, 0), Ms(rson, 0), Ms(data, 0);
Ms(rnd, 0), Ms(sze, 0), root = tot = 0, seed = 1;
}

inline int _rand(void) { return seed *= 482711; }
inline void pushup(int pos) { sze[pos] = sze[lson[pos]] + sze[rson[pos]] + 1; }
inline void split(int pos, int val, int &x, int &y) {
if (!pos) { x = y = 0; return; }
if (data[pos] <= val) x = pos, split(rson[pos], val, rson[pos], y);
else y = pos, split(lson[pos], val, x, lson[pos]); pushup(pos);
}

inline int merge(int x, int y) {
if (!x || !y) return x + y;
if (rnd[x] < rnd[y]) return rson[x] = merge(rson[x], y), pushup(x), x;
else return lson[y] = merge(x, lson[y]), pushup(y), y;
}

inline void insert(int val) {
int x, y, pos = ++tot;
data[pos] = val, sze[pos] = 1, rnd[pos] = _rand();
split(root, val, x, y);
root = merge(merge(x, pos), y);
}

inline void remove(int val) {
int x, y, z;
split(root, val - 1, x, y);
split(y, val, y, z); if (!y) return;
y = merge(lson[y], rson[y]);
root = merge(x, merge(y, z));
}

inline int query_rank(int val) {
int x, y, ret;
split(root, val - 1, x, y);
ret = sze[x] + 1; root = merge(x, y);
return ret;
}

inline int select(int kth) {
int pos = root;
while (kth != sze[lson[pos]] + 1)
if (kth <= sze[lson[pos]]) pos = lson[pos];
else kth -= sze[lson[pos]] + 1, pos = rson[pos];
return data[pos];
}

inline int pred(int val) { return select(query_rank(val) - 1); }
inline int succ(int val) { return select(query_rank(val + 1)); }
} treap;