$\LARGE{引入}$

$\textrm{fhq-treap}$ 是一种不支持旋转的 $\textrm{treap}$ ，由范浩强发明。

$\textrm{treap}$ 就是指 $\textrm{tree} + \textrm{heap}$ ，即二叉搜索树 $+$ 堆。

$\LARGE{概念}$

$\textrm{fhq-treap}$ 对于每一个点维护两个值， $key$ 和 $val$ ，$key$ 为树上排序的指标，$val$ 为一个随机值，保证 $\textrm{fhq-treap}$ 的时间复杂度。

对于 $key$ ，满足二叉搜索树性质，即对于每一个点 $x$ ，其左子树中 $key$ 小于它，右子树中 $key$ 大于它。

对于 $val$ ，满足小根堆性质，即对于每一个节点，它永远是以它为根的子树中 $val$ 值最小的。

$\LARGE{基本操作}$

$\textrm{fhq-treap}$ 有两个基本操作 : $\textrm{split}$ 和 $\textrm{merge}$ 。

$\large{\textrm{split}}$

$split$ 的功能是将一个树按 $key$ 值小于等于 $k$ 和大于 $k$ 划分成两棵树。

具体步骤是先判断根节点属于哪一棵树，若小于等于 $k$ ，则继续分割其右子树，否则分割左子树。

void split(int x, int k, int &l, int &r) { //l,r用于获取分割后两棵树的根节点
    if (!x) {
        l = 0, r = 0;
        return;
    } else if (tr[x].key <= k) { //属于左树
        l = x;
        split(tr[x].s[1], k, tr[x].s[1], r);
        pushup(x);
    } else { //属于右树
        r = x;
        split(tr[x].s[0], k, l, tr[x].s[0]);
        pushup(x);
    }
}

$\large{\textrm{merge}}$

$merge$ 操作是将两颗树按照 $val$ 合并起来，但操作前提是 $l$ 中的 $key$ 必须小于 $r$ 中的所有 $key$ 。

操作步骤是先比较两树根节点的 $val$ ，较小者为根，

若 $l$ 为较小者，由于要维护 $key$ 的顺序，继续将 $l$ 的右子树和 $r$ 合并，左子树保留，

若 $r$ 为较小者，同理将 $r$ 的左子树和 $l$ 合并，右子树保留。

int merge(int x, int y) {
    if (!x || !y) return x | y;
    if (tr[x].val < tr[y].val) {
        tr[x].s[1] = merge(tr[x].s[1], y);
        pushup(x);
        return x;
    } else {
        tr[y].s[0] = merge(x, tr[y].s[0]);
        pushup(y);
        return y;
    }
}