可并堆：一种支持插入、删除、修改、删除任意一个元素、求 \(\min\) 还有合并的数据结构。
下面的只讲可并堆中的一种：左偏树。
左偏树是二叉树，但并不是完全二叉树。它满足两个性质：① 每个结点的权值都小于等于儿子。② 每个结点 \(dist(L)\ge dist(R)\)，\(L,R\) 分别是该结点的左右儿子。
什么是 \(dist()\)？在这之前，先定义 “外结点”：如果一个结点只有一个儿子或者没有儿子，则称它为 “外结点”。
再定义 \(dist(v)\) 为 （\(v\) 的子树中距离 \(v\) 最近的外结点）与 \(v\) 的距离。
容易发现，左偏树的高度实际上是 \(O(n)\) 的。但是我们能找到一些神奇的性质。
性质一：\(dist(v)=dist(v.R)+1\)，这挺显然的，因为 \(dist(L)\ge dist(R)\)。
性质二：若 \(dist(v)=k\)，则 \(sz[v]\ge 2^{k+1}-1\)。
可以用归纳法证明，发现最少的情况就是 $v$ 的子树是一颗高度为 $k$ 的满二叉树。
重要性质：从一个结点往右走，最多走 \(O(\log n)\) 步。
证明：结点 \(u\) 往右走的步数就是 \(dist(u)\)，由性质二知 \(dist(u)\le \log n\)，所以步数 \(O(\log n)\)。
接下来我们看一下这些操作。
-
Merge，合并两颗左偏树。假设合并两颗左偏树的根是 \(a,b\)，不妨设 \(a.key<b.key\)（否则 \(swap\) 一下），则令 \(a.L\) 为 \(a.L\)，\(a.R\) 为 \(Merge(a.R,b)\) 返回的根结点。再判断如果 \(dist(a.L)<dist(a.R)\)，则交换 \(a.L,a.R\)。
记得返回此时的根结点 \(a\)。
时间复杂度是 \(O(\log n)\) 的，因为每次递归都是往右走的，而往右至多会走 \(O(\log n)\) 步，所以复杂度 \(O(\log n)\)。
-
Insert，插入一个数，就是和一个单独的结点 Merge。
-
Query，查询最小值，返回根结点即可。
-
Delete Min，删除最小值。把根结点的左右儿子合并。
-
Delete u，删除任意一个结点 \(u\)，需要提前给出结点编号。合并 \(u\) 的左右子树，令 \(u\) 为合并后的新根结点，然后此时分两种情况。
-
\(dist(u)\) 增加了，则看一下 \(u\) 是它父结点的左儿子还是右儿子。如果是左儿子，啥也不干；如果是右儿子，先判断是否已经比左子树的 \(dist\) 大了，如果是，交换子树。然后再更新父结点的 \(dist\)。
更新了父结点的 \(dist\) 之后，再递归更新父结点的父结点，以此类推。
-
\(dist(u)\) 减少了，如果 \(u\) 是右儿子，更新父结点的 \(dist\)，然后递归看一下父结点是左儿子还是右儿子，一路往上更新；如果 \(u\) 是左儿子，看一下要不要交换左右子树，交换了也要更新父结点，再一路往上更新。
删除任意一个结点需要额外记录这个结点的父亲是谁，是父亲的哪个儿子。
-
模板题。除了要套一个并查集快速查询所在左偏树的根结点，注意不要按秩合并。
这题和上一题极其相似，只是注意多个最小值优先删除编号小的，于是我们在 Merge 的时候看一下两个根如果值相等，让编号小的先上。
if (a[L].val > a[R].val)
swap(L, R);
变成
if (a[L].val > a[R].val || (a[L].val == a[R].val && L > R))
swap(L, R);
每一个结点开一个最小根左偏树，一开始每个骑士都记录在它 \(c_i\) 的左偏树里。
然后进行一次 DFS，到一个结点 \(u\)，先递归处理它的所有儿子；处理完之后，再遍历所有儿子的左偏树，只要当前的左偏树的根小于 \(u\) 的防御值，就 del_min。
此时所有儿子的左偏树存着所有打到结点 \(u\) 的骑士，把这些左偏树全部 Merge 起来，然后在根结点处打一个标记，以后但凡考虑这颗左偏树里的结点，都要考虑标记，而且每当 Merge 和 del_min，都要记得 pushdown。
注意标记有两维：一维是乘法标记，一维是加法标记，和 线段树2 一样。
标签：,结点,dist,log,val,儿子,左偏 From： https://www.cnblogs.com/FLY-lai/p/18000577