一种简易树分块

critnos · 2022-03-26 18:20:36 · 题解

upd：

top cluster 树分块由于其复杂性和常数较大的原因，使用起来比较麻烦。

这里给出一种平凡的简易树分块。

设块长为 B。考虑如下构造：

• 初始存在点集包含整棵树。
• 取出点集中子树大小 size 最大的点 x。
• 若 size_x > B，则删除点集中被包含在 x 的子树中且距离 x 不超过 B 的点。显然，这里标记 \Omega (B) 个点。然后将 x 加入另一点集 S。
• 若 size_x \le B 或点集为空，终止该过程。

显然，上面得到 O(\dfrac n B) 个点。

最终的树分块结构即为点集 S 的虚树 T 上的点。称 T 中的点为关键点。

显然有以下性质：

• 每个点最深的为关键点的祖先距离其距离为 O(B)。
• 每个关键点到其最深的为关键点的祖先距离之和 O(n)（虚树链不相交）。

链上数颜色

预处理两两关键点之间的答案，O(\dfrac {n^2} B)。

考虑 x,y 最深的为关键点的祖先 x',y'，路径拆成 x \to x' \to y'\to y。

枚举 x\to x',y'\to y 上的点，求其在 x'\to y' 上的出现次数即可。

考虑虚树的特性，z=lca(x',y') 也为关键点。利用树上前缀和相减即可。O(nB)。

取 B=\Theta(\sqrt n)，时间复杂度为 O(n\sqrt n)。

链上逆序对

为了使题目更加简洁，令边带权而并非点带权。

和序列上完全一致。令 B=\Theta (\sqrt n)

除了前缀和变成了树上的之外，没有任何区别。