数据结构 4
Published:
可持久化
标记永久化
不下传标记，只在查询的时候考虑。
Path Copy
线段树、Trie、左偏树、无旋 Treap
注意到无旋 Treap 每次修改 $\log$ 个点，path copy
例题
P5283 [十二省联考 2019] 异或粽子
$O((n+k) \log V)$
可持久化做法
TODO:
无可持久化做法
TODO:
P5283 [十二省联考 2019] 异或粽子【$k$ 无限制】
用二分求第 $k$ 大
TODO:
$\sum\limits_{v \in S} (v \oplus s_i)$，拆位维护 $\Theta(\log V)$ 个前缀和
$O(n \log^2 V)$
P3402 可持久化并查集
不能路径压缩（均摊复杂度，错的）。
启发式合并，用可持久化数组维护 $fa$ 和 $siz$。$O(n \log^2 n)$。
BZOJ4668 冷战 (Hard)
https://oi-wiki.org/topic/dsu-app/ B 题加强版。
有 $n$ 个点。$m$ 次操作：
- 添加一条边。
- 询问两点在哪次操作后连通。
强制在线。$1 \le n,m \le 5 \times 10^5$。
神题。这题揭示了并查集背后的图论结构。
我们考虑维护一个有根的生成森林，其连通性和当前的并查集一致，我们称其为并查集生成树（森林）。具体来说，我们要连接 $u,v$，我们就找到各自的代表元 $U,V$ 连起来，如果加边时出现环则不加这条边。使用启发式合并，其树高可以维持在 $O(\log n)$。
这其实就是启发式合并并查集，不加路径压缩。路径压缩会破坏结构，但是启发式合并是无损的。
把并查集看作图论结构的好处在于，我们可以用图论方式解决问题。我们可以把每条边的权值设为加这条边的时间；查询 $u \leftrightsquigarrow v$ 即为查询树上路径的最大值。
由于树高是 $O(\log n)$ 的，路径长度也是 $O(\log n)$，暴力查就完了。
时间复杂度 $O((n + m) \log n)$。
并查集建树还有另一种结构：每次找到 $U,V$ 后不直接连起来，而是新建一个节点 $c$，连 $U \to c$ 和 $V \to c$。注意因为有新建节点的存在，$U,V$ 可能不是原树节点，而是前面的新建节点。我们通过精心设计 $c$ 的权值，就可以用树论的方式解决一些并查集相关问题（当然这种结构就没有树高的优势了）。这棵树称为并查集操作树。
一个典型的例子是 Kruskal 重构树。对于一些瓶颈路问题，我们会采取离线后将边按边权排序后，一边加边一边查询，用并查集维护连通性（例如《数据结构 1》中的 P4197）。
但是如果查询强制在线怎么办？我们预处理时依然先把边排序依次加入，每次加边时将新建节点 $c$ 的权值设为边权。我们发现这棵树的结构除了新建节点以外和 Kruskal 建最小生成树结构很像，因此这棵树得名 Kruskal 重构树。
原图 $u,v$ 间的最小瓶颈路的瓶颈就等于 $u,v$ 在最小生成树上的路径最大值，又等于这棵新树上的 $u,v$ LCA 的权值。
💡[权限题] 大茶馆
NOIP 冲刺计划【2023 / 前期】第六场模拟赛
有一张 $n$ 个点的图，初始时没有边。$m$ 次操作：
- 加一条边。
- 给定一个点 $u$，将 $u$ 所在连通块内所有点两两连边。
- 求两个点 $u,v$ 之间的边数。
$n \le 10^5, m \le 3 \times 10^5$。
边数贡献来源于两部分：操作 1 的直接 Hash 表统计掉，考虑操作 2。
我们在并查集操作树上考虑：操作 $2$ 可以被表示为，在 $u$ 的代表元 $U$ 上打一个子树 $+1$ 标记；操作 $3$ 表示为，查询 $\text{LCA}(U,V)$ 到根的路径上的标记和（树上前缀和）。
我们离线建出并查集操作树即可。
时间复杂度 $O((n + m) \log n)$。
TODO: 我怎么感觉直接并查集生成树就是对的？
P3295 [SCOI2016] 萌萌哒 (Hard)
给定序列长度 $n$。你不知道序列具体元素，但是你知道 $m$ 个关系，每个关系形如：$[l_1, r_1]$ 与 $[l_2, r_2]$ 两个区间内的元素完全相同。
求出最后序列中最多有几个不同元素。
$1 \le n,m \le 10^5$。
神题。这个题可以作为“倍增并查集”的模板题。
我们考虑类似优化建图的想法。首先线段树优化是不优的，因为区间相同是可叠加的，因此使用 ST 表的结构。
我们建立 $O(\log n)$ 层。第 $i$ 层第 $j$ 个节点 $x_{i,j}$ 代表区间 $[j, j + 2^i)$。
对于每个关系，我们求出 $i = \lfloor \log_2 (len) \rfloor$，拆成 $x_{i,l_1} = x_{i,l_2}$ 和 $x_{i,r_1-2^i+1} = x_{i,r_2-2^i+1}$。
最终统计时，我们根据第 $i$ 层的并查集结构更新 $i-1$ 层的并查集。
若 $x_{i,u} = x_{i,v}$，则我们在 $i-1$ 层建立 $x_{i-1,u} = x_{i-1,v}$ 和 $x_{i-1,u+2^{i-1}} = x_{i-1,v+2^{i-1}}$。
具体实现是：枚举 $u$，找到其并查集的最高点 $v = \text{find}{i}(u)$，在 $u,v$ 之间做刚才说的操作。而不是在每一对 $x{i,u} = x_{i,v}$ 之间做。
最终第 $0$ 层就是真实的并查集，直接统计即可。
#14. 【UER #1】DZY Loves Graph
Trick 离线 & 撤销的不是撤销 -> 势能分析
TODO:
可并堆
平衡树可以完全覆盖可并堆的功能……但是可并堆常数小。
TODO:
可持久化无旋 Treap
无旋 Treap：随机权满足堆的性质，权满足 BST 的性质
TODO:
P5055 【模板】可持久化文艺平衡树
模板题。
TODO: