可持久化

标记永久化

不下传标记，只在查询的时候考虑。

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 冷战

神题。

我想的：倍增 + LCA，时间 1log，空间 1log

Trick TODO:

P3295 [SCOI2016] 萌萌哒

神题。

倍增并查集

连边 $(i,j) \leftrightarrow (\text{find}_{j+1}(i), j)$

TODO:

#14. 【UER #1】DZY Loves Graph

Trick 离线 & 撤销的不是撤销 -> 势能分析

TODO:

可并堆

平衡树可以完全覆盖可并堆的功能……但是可并堆常数小。

P3377 【模板】左偏树/可并堆

TODO:

可持久化无旋 Treap

无旋 Treap：随机权满足堆的性质，权满足 BST 的性质

TODO:

P5055 【模板】可持久化文艺平衡树

模板题。

TODO: