左偏树

左偏树是一种可并堆，学来做 \(slope-trick\) 。

左偏树满足堆的性质，以及一个新的左偏性质。

先放定义：定义外部节点为没有左儿子或右儿子的节点。定义一个节点的距离(dis)为它到子树内最近的外部节点的距离，特别的，空节点的 \(dis\) 为 -1 。这是为了打代码方便，使得外部节点的 \(dis\) 可以初始化为 0。

根据这个定义，可以推出一棵以 \(x\) 为根的二叉树的大小至少为 \(2^{dis_x+1}-1\) ，同时也可以推出：对于一棵有 \(n\) 个节点的二叉树，其根节点的 \(dis\) 至多为 \(\left\lceil\log(n+1)\right\rceil\) 。

左偏性质即为对于每个点 \(x\) ，都有 \(dis_{ls}\ge dis_{rs}\) 。

合并

可并堆最重要的就是合并了！

对于两个小根堆的根 \(x,y\) ，假设 \(x<y\) ，不满足就交换。则 \(x\) 一定为当前子树的根。由于左偏，所以我们将 \(y\) 与 \(x\) 的右子树向下递归合并。回溯的时候要维护左偏性质，即判断路径上的每一个点 \(x\) 是否都有 \(dis_{ls}\ge dis_{rs}\) ，不满足就交换。时间复杂度为 \(O(\log n+\log m)\) ，其中 \(n,m\) 为合并的两个堆的大小。

其他操作

加入：直接当作合并来做

删除：若删除的点为根，则直接合并左右子树就好。若删除的点不为根，则需要额外维护每个点的父节点，并且在合并完儿子后，需要向上维护左偏性质。