rerererecollector

H_Kaguya · 2026-03-09 16:24:59 · 休闲·娱乐

还在使用 recollector 剖分？
详细解密如何把 recollector 剖分维护树链信息卡到 \tilde O(\frac{n^2}{\log n})！

考虑我们构造这样一棵树：
令根节点为 1，然后 \forall i \in [1, n)，连接 i \to i+1 和 i \to i + n 的边。
不难发现这就是一个简单的链挂点的结构。

好了，接下来我们将要证明，期望意义下点 n 上方轻边的个数是 \tilde O(\frac{n}{\log n}) 的。

不妨直接考虑 n 上方重链的期望长度 E。
连续 k 次被选为重边的概率 P(k) = \prod \limits _{i = 1}^{k} \frac{i}{i + 1}
诶，这是什么，这不是我们 \frac{1}{k + 1} 吗

所以可以得到 E = \sum \limits _{k = 1} ^{n} P(k - 1) = H_n \in \Theta(\log n)

然后就做完了。考虑上方剩余的点的数量不小于 \sqrt n 的时候，直接取 E = \log n 算即可，这部分的轻边数量就是 \tilde O(\frac{n}{\log n})。上方剩余点小于 \sqrt n 的时候就无所谓了，这部分的贡献 o(\sqrt n) 直接扔掉就行了。
直接一直查询 n 就可以把复杂度卡到 \tilde O(\frac{nm}{\log n}) 了，取 n, m 同阶就得到 \tilde O(\frac{n^2}{\log n}) 了！

可恶怎么有水印

Bonus：在链上面每个位置挂两个单点就可以把轻边数量卡到 \tilde O(n)，大家可以自己证一下。