可持久化

乱写一气。

可持久化线段树

P3402 可持久化并查集

按秩合并，将并查集的 \(\mathrm{fa}\) 和 \(\mathrm{size}\) 数组可持久化。时间 \(\mathcal{O}(n+m\log^2 n)\)。

P3293 [SCOI2016] 美味

从高位到低位确定答案，对每一位都在可持久化线段树上二分一下。时间 \(\mathcal{O}(n\log n+m\log^2 V)\)。

P3302 [SDOI2013] 森林

假如我们知道了一棵树上每个点到根的路径上的、由点权组成的可持久化线段树，那么我们可以在 \(u,v,\operatorname{LCA}(u,v),\operatorname{fa}(\operatorname{LCA}(u,v))\) 四棵可持久化线段树上同时二分，来求得 \(u,v\) 间的链上的第 \(k\) 小。

连边时，采用启发式合并，暴力重构较小的连通块的倍增表和可持久化线段树。

假设 \(n,q\) 同阶，由于每个点最多被重构 \(\mathcal{O}(\log n)\) 次，每次在线段树上最多添加 \(\mathcal{O}(\log V)\) 个点，所以线段树的空间要开到 \(\mathcal{O}(n\log n\log V)\)，离散化后可以做到 \(\mathcal{O}(n\log^2 n)\)。时间复杂度也是 \(\mathcal{O}(n\log^2 n)\)。

写错的地方：倍增求 \(\operatorname{LCA}\)，两个点同时往上跳时，\(i\) 要从大到小枚举。

Kruskal 重构树

其实和可持久化没什么关系。

类似 Kruskal 求解 MST 的过程，我们将所有边按边权从小到大排序，对于每一条有用的边 \((u,v,w)\)，我们找到 \(u,v\) 所在的连通块在重构树上的根节点 \(x,y\)。我们新建一个点 \(f\)，它是重构树上 \(x\) 和 \(y\) 的父亲，且它的点权为 \(w\)。

这个过程会添加恰好 \(n-1\) 个点，这些新点都有恰好两个儿子，且其他 \(n\) 个点没有儿子。并且这棵重构树是一个大根堆，所以：

• 两个点之间的最小瓶颈路的边权最大值就是重构树上它们的 LCA 的点权；
• 与一个点 \(u\) 之间的最小瓶颈路的边权最大值小于等于某个数的点，都在 \(u\) 的某个祖先的子树内，且这个子树内的所有叶子节点都满足这个条件。

LOJ 137 最小瓶颈路 加强版

建出 Kruskal 重构树，然后问题就变成了询问 LCA。用欧拉序转成 RMQ 问题，可以做到单次询问 \(\mathcal{O}(1)\)。

于是也得到了 \(\mathcal{O}(1)\) 询问链上 \(\min\) 的做法！

P4197 Peaks

建出 Kruskal 重构树，问题就变成了子树第 \(k\) 大，可持久化线段树即可。

代码：https://www.luogu.com.cn/paste/jaxab4su。

P4899 [IOI2018] werewolf 狼人

建两棵 Kruskal 重构树，一棵的边权为 \(\min(u,v)\)，另一棵的边权为 \(\max(u,v)\)。我们将每个点放在 dfn-dfn 二维平面上，平面的 \(x\) 轴是第一个重构树的 dfn，\(y\) 轴是第二棵的。然后就变成了二维数点。

代码：https://uoj.ac/submission/532885。