题解【P8157 「PMOI-5」肥宅の水】

jerry3128 · 2022-02-15 10:27:58 · 题解

抢救笛卡尔树

• 首先考虑笛卡尔树计算静态答案，直接建树后在每个节点的子树大小乘上其高度即可。
• 考虑当高度互不相同的时候，并且 n 和 q 同阶，容易得到均摊 \mathcal O(1) 次旋转可以完成对笛卡尔树形态变化的维护。
• 那么也就是说我们要解决的问题就是当多个节点有同一个高度的时候，我们旋转的 Worst Case 是节点个数的。
• 那么在特意构造的情况下，旋转次数可以被卡到 \mathcal O(n)。
• 那么我们需要解决的问题就是：使得每一节点，在向上旋转而跨越某一高度的时候，能够有能被接受的旋转次数。
• 我们考虑将笛卡尔树按 各个有相同键值 的连通块划分，对于每个连通块我们单独分析复杂度。那么我们需要支持的操作是：旋转到根、将一个单点插入到父亲联通块中。

方法一：随机第二键值

• 考虑到笛卡尔树本质上是用旋转维护的二叉堆。
• 那么我们容易想到另外一个二叉平衡树单旋 Treap，它也用一个随机键值来维护平衡树，使得树高在期望 \log 的高度。
• 那么在一个节点高度减一的时候，我们期望将它旋转 \mathcal O(\log n) 次，并且在同阶的复杂度内维护新树的形态。
• 又因为需要使用一个数据结构维护全局答案最大值，multiset 是一个例子。那么就有复杂度期望 \mathcal O(n\log^{2}n)，基于手动随机的第二键值。

方法二：强制双旋

• 考虑到单旋的父子该变量为 \mathcal O(1)，所以可以被卡。所以使用双旋。
• 考虑双旋的复杂度分析：
  1. 对于 h_{x}<h_{fa_{x}}
     • 在父亲点、爷爷点二者的高度相同时直接使用双旋。
     • 否则，只会有 \mathcal O(1) 次例外情况，即 x 父亲为根的情况。
     • 此时对于当前连通块双旋复杂度均摊分析成立。
  2. 在 1 之后，对于 h_{x}=h_{fa_{x}}
     • 将一个节点双旋至根即可。
     • 否则，只会有 \mathcal O(1) 次例外情况，即 x 父亲为根的情况。
• 然后写出来之后你发现这个东西跟 splay 森林没区别。所以有复杂度 \mathcal O(n\log^{2}n)。

上述两种方法的两只 \log 均十分小，所以跑过 5\times 10^{5} 应该是没有问题的。