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;
}