FHQTreap
\(\text{FHQ Treap = Tree + Heap}\)
FHQTreap 通过给节点赋一个随机数，当作这个点的优先级，通过随机化让平衡树尽可能的平衡。令人惊喜的是，FHQTreap 的中序遍历能得到原来的序列。那么，我们应该如何维护 FHQTreap 呢？
存储
我们需要以下变量来存储：
struct FHQTreap{
int ch[N][2] /*0为左儿子 1为右儿子*/ , val[N] /*节点的值*/ , key[N] /*节点的优先级*/, siz[N] /* 以该节点为根的子树的大小（包括它本身）*/, root /*树的根*/, cnt /*节点个数*/;
} T;信息上传
我们在进行一些操作的时候，可能要将儿子的信息传到父亲身上。
inline void PushUp(re int rt) {
siz[rt] = siz[ch[rt][0]] + siz[ch[rt][1]] + 1; //以左儿子为根的子树+右儿子为根的子树+它本身即为1
}新建节点
新建一个节点。
inline int NewNode(re int v) {// v 为新建的节点的值
siz[++cnt] = 1; val[cnt] = v; key[cnt] = rand()/*随机一个优先级*/;
return cnt;
}合并子树
重要的操作，合并两个子树。
我们要按照优先级来合并两个子树，我们这里规定，如果子树 \(x\) 的优先级比 \(y\) 高（\(key_x < key_y\)），那么我们将子树 \(y\) 合并到子树 \(x\) 的右儿子上。否则，我们将子树 \(x\) 合并到子树 \(y\) 的左儿子上。合并之后，需要把改变后的信息上传到父节点。
int Merge(re int x, re int y) {//将x和y合并返回合并后的子树的编号
if (!x || !y) return x + y;//如果有任何一个子树为空，那么返回另一个（如果两个都是空返回0）
if (key[x] < key[y]) {
ch[x][1] = Merge(ch[x][1], y);
PushUp(x); return x;
} else {
ch[y][0] = Merge(x, ch[y][0]);
PushUp(y); return y;
}
}分裂子树
和合并子树一样重要，我们有两种分裂方法：一个是根据权值分，另一个是根据大小分。这道题最方便的方法是用权值分，大小分下面会讲。
用权值怎么分呢？我们可以将所有点权小于等于传入的参数的点分裂到左子树，其他的分裂到右子树。递归求解即可，最后我们将分裂后子树的信息上传。
void Split(re int rt, re int v, re int &x, re int &y) {//带&方便修改
if (!rt) x = y = 0;
else {
if (val[rt] <= v) {
x = rt;//分给右子树
Split(ch[rt][1], v, ch[rt][1], y);
} else {
y = rt; //分给左子树
Split(ch[rt][0], v, x, ch[rt][0]);
}
PushUp(rt);//上传
}
}插入节点
我们先把树分为 \(x,y\) 两部分，然后把新的节点看做是一棵树，先与 \(x\) 合并，合并完之后将合并的整体与 \(y\) 合并。
inline void Insert(re int v) {
re int x, y;
Split(root, v, x, y);
root = Merge(Merge(x, NewNode(v)), y);
}删除节点
首先我们把树分为 \(x\) 和 \(z\) 两部分，设我们删除节点的权值为 \(a\)，再把 \(x\) 分为 \(x\) 和 \(y\) 两部分，使得 \(x\) 中节点的权值全部小于 \(a\)，\(y\) 中的全部大于 \(a\)。这就相当于我们传进的参数 \(v = a - 1\)。 而且呢，权值为 \(a\) 的节点正好是 \(y\) 树的根。 然后我们可以无视 \(y\) 的根节点，直接把 \(y\) 的左右孩子合并起来，这样就成功的删除了根节点，最后再把 \(x,y,z\) 合并起来就好。结合下面丑图理解：
inline void Delete(re int v) {
re int x, y, z;
Split(root, v, x, z);
Split(x, v - 1, x, y);
y = Merge(ch[y][0], ch[y][1]);
root = Merge(Merge(x, y), z);
}求一个数的排名
考虑二叉查找树的性质：左儿子的值比父亲的小，右儿子的值比父亲大。那么，一个数的排名就是所有比它小的数加上他自己。简单吧？
inline int Lvl(re int v) {
re int x, y, res;
Split(root, v - 1, x, y);
res = siz[x] + 1;
root = Merge(x, y); //分裂后别忘合并
return res;
}求排名为任意值的数
从根节点出发。根据二叉查找树的性质，如果当前点的值比所在点的值大，那么向右子树走，否则向左子树走。如果排名正好相等就返回值，while 循环就可以解决。可是真的那么简单吗？不，我们向右子树走的时候，左子树会有许多比它权值小的节点，所以我们要减去它左子树的大小。向左子树走的话直接走就可以了。
inline int Kth(re int rt, re int v) {
while (1) {
if (v <= siz[ch[rt][0]])
rt = ch[rt][0];
else if (v == siz[ch[rt][0]] + 1)
return val[rt];
else {
v -= siz[ch[rt][0]] + 1;
rt = ch[rt][1];
}
}
}求一个数的前驱
因为要小于 \(a\) ，那么我们按照 \(a-1\) 的权值分裂成 \(x\) 和 \(y\) ，\(x\) 中最大的一定是\(\leq a - 1\)的，所以我们直接输出 \(x\) 中最大的数即可。
inline int Pre(re int v) {
re int x, y, res;
Split(root, v - 1, x, y);
res = Kth(x, siz[x]);
root = Merge(x, y);
return res;
}求一个数的后继
与求前驱相似，我们只需修改找 \(\ge a\) 的最小的数就可以了。
inline int Suf(re int v) {
re int x, y, res;
Split(root, v, x, y);
res = Kth(y, 1);
root = Merge(x, y);
return res;
}完整模板
#include <bits/stdc++.h>
#define N 100005
#define re register
#define inline inline
using namespace std;
int n;
struct FHQTreap {
int ch[N][2], val[N], key[N], siz[N], root, cnt;
inline void PushUp(re int rt) {
siz[rt] = siz[ch[rt][0]] + siz[ch[rt][1]] + 1;
}
inline int NewNode(re int v) {
siz[++cnt] = 1; val[cnt] = v; key[cnt] = rand();
return cnt;
}
int Merge(re int x, re int y) {
if (!x || !y) return x + y;
if (key[x] < key[y]) {
ch[x][1] = Merge(ch[x][1], y);
PushUp(x); return x;
} else {
ch[y][0] = Merge(x, ch[y][0]);
PushUp(y); return y;
}
}
void Split(re int rt, re int v, re int &x, re int &y) {
if (!rt) x = y = 0;
else {
if (val[rt] <= v) {
x = rt;
Split(ch[rt][1], v, ch[rt][1], y);
} else {
y = rt;
Split(ch[rt][0], v, x, ch[rt][0]);
}
PushUp(rt);
}
}
inline void Insert(re int v) {
re int x, y;
Split(root, v, x, y);
root = Merge(Merge(x, NewNode(v)), y);
}
inline void Delete(re int v) {
re int x, y, z;
Split(root, v, x, z);
Split(x, v - 1, x, y);
y = Merge(ch[y][0], ch[y][1]);
root = Merge(Merge(x, y), z);
}
inline int Lvl(re int v) {
re int x, y, res;
Split(root, v - 1, x, y);
res = siz[x] + 1;
root = Merge(x, y);
return res;
}
inline int Kth(re int rt, re int v) {
while (1) {
if (v <= siz[ch[rt][0]])
rt = ch[rt][0];
else if (v == siz[ch[rt][0]] + 1)
return val[rt];
else {
v -= siz[ch[rt][0]] + 1;
rt = ch[rt][1];
}
}
}
inline int Pre(re int v) {
re int x, y, res;
Split(root, v - 1, x, y);
res = Kth(x, siz[x]);
root = Merge(x, y);
return res;
}
inline int Suf(re int v) {
re int x, y, res;
Split(root, v, x, y);
res = Kth(y, 1);
root = Merge(x, y);
return res;
}
} T;
int main() {
scanf("%d", &n);
for (re int i = 1; i <= n; i++) {
re int opt, x;
scanf("%d %d", &opt, &x);
if (opt == 1) T.Insert(x);
else if (opt == 2) T.Delete(x);
else if (opt == 3) printf("%d\n", T.Lvl(x));
else if (opt == 4) printf("%d\n", T.Kth(T.root, x));
else if (opt == 5) printf("%d\n", T.Pre(x));
else if (opt == 6) printf("%d\n", T.Suf(x));
}
return 0;
}