这是本文档旧的修订版!
一种可并堆,支持 $O(\log n)$ 的 $\text{push}$、$\text{pop}$、$\text{merge}$ 操作。
定义外节点为左儿子或右儿子为空的节点,$\text{dist}_i$ 表示节点 $i$ 到其子树中最近外节点的距离,规定空节点的 $\text{dist}$ 为 $-1$。
左偏树的定义为对每个节点 $u$ 均满足 $\text{dist}_\text{lson}\ge \text{dist}_\text{rson}$ 的堆。
左偏树有如下性质
关于性质一,有 $\text{dist}_u=\max(\text{dist}_\text{lson},\text{dist}_\text{rson})+1=\text{dist}_\text{rson}+1$,证毕。
关于性质二,有 $\text{dist}_u$ 表示节点 $u$ 到其子树中最近外节点的距离,所以有节点 $u$ 的子树的前 $\text{dist}_u$ 层均为非外节点。
所以可将前 $\text{dist}_u$ 层视为满二叉树,第 $\text{dist}_u+1$ 层至少有一个外节点,所以有 $\text{sz}_u\ge 2^{\text{dist}_u}$,证毕。
考虑左偏树的合并操作,类似 $\text{fhq treap}$ 的 $\text{merge}$ 操作,根据优先级(这里是点权)不断合并两棵树,遇到空结点返回。
不同之处在于合并两棵左偏树时对跳左节点还是右节点没有限制,所以强制每次跳右节点,使得 $\text{dist}_u$ 单调递减。
这样,时间复杂度为 $O(\text{dist}_u)=O(\log n)$。
左偏树的另一个核心操作为寻根,事实上寻根操作可以利用路径压缩的并查集优化时间复杂度到 $O(\log n)$,但需要注意一些细节,详细见代码。
左偏树的 $\text{pop}$ 操作类似 $\text{fhq treap}$,直接合并被删除节点的左右儿子,但是删除祖先节点会导致并查集出错。
具体解决方案为 root[p]=root[node[p].ch[0]]=root[node[p].ch[1]]=rt
,即把原堆顶元素及其儿子节点的祖先节点指向新根节点。
维护 $n$ 个堆,每个堆一开始只有一个元素,$m$ 个操作。
每次选取两个堆,将堆顶元素减半,然后合并。
修改堆顶元素方法为先合并左右儿子,然后修改堆顶,再次加入。同样要注意并查集的维护。