LCT 维护树分块

· · 题解

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 吧，至少上高中之后了。