自动搬运

查看原文

来自洛谷，原作者为

	EnofTaiPeople MGXS

搬运于2025-08-24 22:45:42，当前版本为作者最后更新于2023-03-08 07:46:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Part1 前言

WBTT 暂时被我认为是考场不可写作的，也就是它把我劝退了。

但本题感觉把 WBTT 写到脸上了，但我说了 WBTT 考场不可写作，所以我没有办法使用 WBTT。

然而，做法依旧是 zx2003 教我的，虽然我没有和他见过面，也不在一个学校。

Part2 考场做法

树分块是平凡且不具有扩展性的，这道题可以归约为 Link-Cut 链加链 rank，放在序列上是经典分块问题。

于是我将 WBTT 中的 WBTT 换成了 LCT 就过了。

具体地，对 LCT 上节点的 $sz$ 做根号分治，在 pushup 时，只有 $sz_x\le\sqrt n$ 才会将两个子树的 vector 归并，这样保证了修改复杂度为 $O(\sqrt n\log n)$。

查询递归到每一棵 $sz_x\le\sqrt n$ 的子树二分就行了，这一步是 $O(\sqrt n\log n)$ 的。

Part3 对低复杂度做法的探讨

然后我考后发现查询复杂度是错误的。

原因是，如果当时 splay 存在较长链，这一步就必须要伸展，否则就不对，不过出题人并没有卡，事实上，我自己就能卡掉。

如果你这一步选择伸展，那么伸展复杂度是 $O(\sqrt n\log n)$ 的，$O(nq\log n)$ 有存在的必要吗？

其实还是有方法的，使用 fhqTreap 就可以了，注意这里需要建 Top Tree，不然 $O(q\sqrt n\log^2 n)$ 也已经渐近暴力了。

直接用 fhqTreap 实现 $\text{Rand Top Tree}$ 是 $O(q\sqrt n\log n)$ 的，这一步我并不会证。

Part4 用常数换复杂度

我要半个 $\log$！虽然半 $\log$ 标算的题目是极少的。

你需要会分散层叠算法。

就是说，即使 $sz_x>B$，我们也进行两个子树的分散层叠合并，然后将 $B\leftarrow\sqrt{\dfrac n{\log n}}$ 于是时空复杂度 $O(n\sqrt{n\log n})$。

然而常数太大了，分散层叠在目前的应用大多数都停留在理论分析。

标算的定期重构树分块是平凡的，即使有较小的常数优势但并不具有可扩展性，我要你真的 Link-Cut 你就没了。

当然，WBTT 必定是严格 $O(n\sqrt n)$ 的。

Part5 后记

我已经下定决心短时间内不再研究 $\text{Top Tree}$ 的更深内容了，一道题似乎并不能让我回来？

希望有一天我能够真正地学会 WBTT 吧，至少上高中之后了。