在这里先膜拜大神 cyx, 五年级就回了(在我旁边切紫题)。
对于一个小根堆, 我们考虑他们的合并, 我们可以通过一种每次和右儿子和另一个节点合并的方式, 用时间复杂度为 \(O(右儿子的深度)\)。这样, 我们就会有个想法, 只需要办证每次左儿子深度 > 右儿子深度, 这样就可以保证时间复杂度为 \(O(\log n)\) 合并。
例题
luogu P4331
首先根据题解我们知道, 我们每次维护后缀中位数即可
虽然这个东西感觉不符合直觉, 但是我们可以伪证一下。
首先先挂一个实现的证明 https://www.luogu.com.cn/discuss/602826。
我们考虑为什么合并两个区间是这两个区间的中位数。
首先, 我们考虑如果其中前面的那个东西保持不变。
我们令前一个的中位数为 \(x\), 后一个的中位数为 \(y\)。
我们考虑前一个位置如果还是保持 \(x\) 不变。
如果你左边的那一块选 \(y\), 右边的那一块选 \(y+\), 则原来一定中位数分布如图, 所以他们不会合并成一个块, 矛盾。
对于右边的快如果不变, 可以用类似的方法证明。
用类似的方法, 我们可以证明合并后前面一块取得值都相等, 后面一块选的值都相等。