NFLS暑假专题3 可持久化数据结构，复杂分块，树套树

_Cheems · 2025-07-22 14:55:42 · 个人记录

By fishpear。远古大神，讲得好啊。

可持久化数据结构

首先是主席树，耳熟能详了属于是，考虑推广一下：

• 假如我们的数据结构是个树且不存储父节点，就能套用主席树的方法。

众所周知，平衡树难以可持久化。主要原因在于旋转操作依赖于父节点，但其实可以在递归过程中存储祖先链到一个数组，就能做到可持久化。当然没人写这玩意。

同时课件指出：fhq treap 本质上是将上述数组用递归时的系统栈存起来，也就是说两种方法是相同的。

然后是区间修改，一般来说我们得写标记永久化，但是真的不能用标记下传了吗？不是的。

最后，对于一般的数据结构也能可持久化吗？可以的，用可持久化数组即可，例子是并查集。不过会多一只 log。

同时，假如只要求回滚，拿个栈存储修改即可。

对于特定问题，存在不带 log 做法。视频链接，当然这玩意不考。

P2839 middle

经典套路：中位数无脑二分答案 mid。

将 \le mid 设为 1，>mid 设为 -1。那么区间中位数 \ge mid 等价于区间和 >0。所以问题变为寻找最大区间和，这是容易的。然后用主席树存下每个 mid 的线段树即可。O(n\log^2n)。

由此提出运用可持久化的基本方法：若发现将询问离线后数据结构可解，将该数据结构可持久化便能在线了。也就是说，可持久化具有强制转在线的作用。

P4899 [IOI 2018] werewolf 狼人（无代码）

题意：无向图，多次询问从 s\to t，变身前只能在 [l,n]，变身后只能在 [1,r]，问是否可行。

枚举变身点，问题转化为 s 只走 [l,n]、t 只走 [1,r] 两个连通块是否存在交集。

联想到 kruskal 重构树，分别从前往后、从后往前加入点，那么两个连通块对应两个森林上的两个子树。使用 dfs 序刻画限制，将点转化为二维数点，坐标分别是两个森林上的 dfs 序，每次询问一个矩形是否有点，主席树即可。

这题重点在于用 kruskal 重构树将连通块转化为子树、并通过 dfs 序转化为二维数点问题。主席树只是工具。

细节：kruskal 重构树按点权构建，只需将边权设为两端点编号最值即可。

P7172 [COCI 2020/2021 #3] Specijacija（无代码，要补）

题意：一棵 n+1 层的树，每一层恰有一个点有两个儿子，其它只有一个，编号从上到下、从左往右。多次询问求 lca(x,y)。

直观想法是倍增跳 lca，问题变为对任意点求任意级祖先。为了解决这个问题，重新编号以观察性质：

从下往上，考虑每个叶子对应该层的哪个点，可以发现，是前缀 [1,p] 编号不变，后缀 (p,n] 编号减一。想到用主席树后缀减、单点查。但是点不一定是叶子，需要找到其子树内一个叶子，需支持寻找 x 对应下标，由于序列有序，树上二分即可。

突破点在于观察到相邻层之间节点编号变化的规律，并联想到运用主席树维护叶子每层对应祖先、以支持倍增。

QOJ970 Best Subsequence（无代码，要补）

题意：给一个数组，多次询问在 [l,r] 中选 k 个数，最小化相邻数之和（包括首尾）的最大值。

较为困难的一题。

二分答案 lim 转判定。然后有一个套路：将 \le \frac {lim}2 的视为 0、>\frac {lim}2 的视为 1。那么 00 一定行，11 一定不行，01 看情况。

贪心地想，先全选 0 肯定不劣。直觉上很对。考虑最优解存在一个 0 不被选，若加入后产生 01 非法，那么将这个唯一存在的 1 去掉即可。

接下来加入 1，对于首尾和相邻 0 之间的 1 显然取最小的，判断能否加入即可。

考虑用数据结构加速这个过程，考虑 lim 从小到大，每次修改 1 变成 0。考虑相邻 0 构成的段，那么总共会有 O(n) 次区间分裂，对于不分裂的区间，会在某个时间由不可选变为可选，拿一个线段树捕捉这些点即可。对于分裂的区间，我们直接取出最小值并标记是否可选即可。

然后用主席树维护即可，O(n\log^2 n)。

这题主要是想到按 \frac {lim}2 分类，然后贪心，并用数据结构进行优化，用可持久化支持二分。

分块

技巧性很强，见例题。

P5046 [Ynoi2019 模拟赛] Yuno loves sqrt technology I（无代码，要补）

题意：求区间逆序对，强制在线，n,q\le 10^5。

大力分块取块长 \sqrt n。

考虑整块与整块，提前排序每次做归并，预处理整块两两间的逆序对数，O(n\sqrt n)。

考虑散块内部，必然是前后缀，用插排即可，O(n\sqrt n)。

考虑散块与整块，相当于求一个数与一个整块，只需在整块与整块部分记录即可。查询 O(\sqrt n)。

考虑散块与散块，从整块排序结果中，提取散块排序后的结果，然后直接归并，查询 O(\sqrt n)。

考虑短区间 [l,r] 在整块 [L,R] 中，考虑容斥，可以直接提取出 [L,l),[l,r],(r,R] 三部分排序后结果，然后归并即可算出三部分互相的逆序对数。单次也是 O(\sqrt n)。

总的就是优美的 O(n\sqrt n)。

这题揭示了分块的基本方法：整块、散块分开讨论。分块一般带 log 是好做的，若要去 log 则需精细实现，技巧性非常强。

CF453E Little Pony and Lord Tirek（无代码，要补）

题意：n 个数初始为 s_i，每秒增长 r_i，上限为 m_i。需支持：时间增长 t；求区间和并马上清空区间。n,q,V\le 10^5。

可以基于颜色段 O(n\log^2 n)，不讨论。

分块，将被不完全推平的段称为特殊段，初始时均为特殊段。散块暴力计算即可。

每次推平时，对特殊段进行暴力计算，并对新产生的特殊段暴力更新。那么特殊段总数为 O(q)，且除首尾外特殊段被计算后不再特殊，那么特殊段部分是 O(nB) 的。

对于非特殊段，只需记录最晚推平时间，那么问题相当于求 \sum \min(t\times r_i,m_i)，可以按填满时间进行二分但是多个 log，由于值域较小其实可以暴力预处理出每个 t 的答案。O(\frac nBV)。

取 B 为 \sqrt n 即可。

这题注意到被完全推平的段好做，而不完全推平的段可以暴力做，通过势能分析得到正确复杂度。

CF1129D Isolation（无代码，要补）

题意：求序列划分方案数，要求每一段恰好出现过一次的数的个数 \le k。n,k\le 10^5。

显然 dp，那么问题为移动右端点、快速查询合法左端点的 dp 值的总和。

数字相对独立，考虑一个数 x，它将序列划分为若干段，那么当右端点在一个区间时合法左端点也在一个对应区间，这样的区间是 cnt_x 个的。总共是 O(n) 的。

将这些区间离线下来扫描线，问题变为：区间 +1,-1，求 \le k 位置的 dp 值的总和。询问难以用线段树维护。

尝试分块，记块长为 B。

注意到对于整块的修改，若一开始对它进行排序并将相同的值相加起来，那只需用一个指针记录合法的前缀，修改只需左右移动指针。这启示我们维护整块有序。

考虑修改，对于散块，暴力重构排序并前缀和。由于本来整块有序，那么修改后得到几个有序序列，将它们归并即可，这样没有 log。对于整块做刚刚的操作即可。

考虑查询，对于整块，因为已经记录了指针可以直接得到答案。对于散块，暴力查询即可。

对于短区间，暴力即可。那么总复杂度是 O(n\sqrt n)。

这题是分块优化 dp，首先要想到数字贡献独立，将“恰好出现一次”转化为 O(n) 个区间的限制。然后得到一个数据结构问题，需要想到维护整块有序方能解决。

P5443 [APIO2019] 桥梁（无代码，要补）

题意：在无向图上支持：修改边权、只走 \ge y 的边求 x 连通块的大小。n\le 5\times 10^4,m,q\le 10^5。可以离线。

显然 kruskal 重构树，假如无修改就很好做了，但是有修改只能暴力重构 kruskal 树。这时要想到套路：对时间序列（操作序列）分块。它的用处是减少重构次数。

分块后，一起处理一个整块的所有询问。对于该块内未修改的边，我们可以将边权排序后跑 kruskal，由于本题可以离线，将询问挂在 y 上便能得到每个询问对应的连通性。然后暴力补上被修改的边，最后使用回滚操作把这些边撤销即可。

取块长 \sqrt q，O(m\sqrt q \log m+q\sqrt q\log n)。

本题是可撤销并查集与时间序列分块的结合。

P7722 [Ynoi2007] tmpq（无代码，要补）

题意：有数组 a,b,c，需支持：单点修改 a、询问有多少个三元组 i<j<k 满足 b_{a_i}=a_j=c_{a_k}。n\le 2\times 10^5,m\le 5\times 10^4。

查询的形式实在是太怪了，不妨令 b_i\gets b_{a_i}，c_i\gets c_{a_i}，那么问题变为单点改 a,b,c，查询 b_i=a_j=c_k。

然后每个数字贡献独立，所以单独考虑。那么显然有 dp，记 f_{i,j} 考虑前 i 位且取了 j 个数字的方案。转移容易。

发现可以根号分治！对于出现次数（原序列次数加操作次数）小于 B 的，直接暴力计算 O(B)。然后考虑查询，相当于总共有 O((n+m)B) 次单点改和 O(m) 次前缀求和，根号一体两面一下 O(1) 改、O(B) 查，总的就是 O((n+m)B) 的。

对于出现次数 >B 的只有 O(\frac {(n+m)}B) 个，注意到 dp 可以用 ddp 的方式维护，注意这样就只能每种数字分别计算然后加起来了。转化为 O(n+m) 次单点改、O((n+m)B) 次前缀积，依旧一体两面，总共 O((n+m)B)。具体来说，考虑修改对后面带来的影响即可。

令 B=\sqrt {n+m} 则 O((n+m)\sqrt (n+m))。

本题需先转化三元组的形式，然后观察到数字独立并使用根号分治，同时分块带来的查询修改往往是 O(n\sqrt n) 的，需要灵活运用一体两面以平衡复杂度。

CF1491H Yuezheng Ling and Dynamic Tree

题意：以 fa_i<i 的形式给一棵树，支持 fa 区间减（最多减到 1）、求 lca(x,y)。n,q\le 10^5。

容易联想到弹飞绵羊，将序列分为 \sqrt n 块，维护每个点第一次跳出整块到达的点。那么便能方便得求出 lca(x,y)，假如 x,y 不在同一块就让靠后的点跳出块；否则，lca(x,y) 在块内当且仅当 x,y 跳出块到达的点相同，此时暴力跳即可。假如我们能 O(1) 跳出块，就能 O(\sqrt n) 回答询问。

考虑怎么修改，对于散块暴力重构。注意到 fa 只减不增，所以对于一个整块其操作次数 \ge \sqrt n 时一步就跳出，打个标记即可；否则就暴力重构。

总共 O((n+q)\sqrt n)。

这题主要是联想到弹飞绵羊，然后观察到 fa 不增的性质来优化修改。

树套树

很暴力这个东西。

考虑外层线段树的东西，单点改、区间查，单点查、区间改都是容易做的。注意外层线段树不能区间改，因为标记无法合并。

CF1080F Katya and Segments Sets

题意：给你 n 个集合，集合元素是区间。m 次询问集合 s_l\dots s_r 是否均存在一个区间为 [x,y] 的子区间。n,m\le 10^5。

套路：区间转二维数点。那么 A 包含 B 等价于 A 在 B 左上角。

考虑一个集合，那么合法的 [x,y] 构成一个上阶梯型，问题相当于判断 s_l\dots s_r 的阶梯的交是否包含 [x,y]。

考虑怎么暴力做，将数点视为序列、其纵坐标为元素值，那么就是每个位置分别取 \max，然后看看 a_x 是否 \le y。

套路：若区间询问复杂，但前后缀询问容易，考虑猫树分治。本质上是将询问区间放在线段树上，则必然存在一个区间包含它且它跨过 mid，也就是能拆为前后缀的形式。

本题可以分别判定前后缀。对于这个问题，每次新增一个集合时相当于做 |s| 次区间取 \max，由于有序可以转为区间推平，势能分析可得复杂度正确。强制在线所以要用主席树。这个做法相当于线段树套主席树，时空间都是两个 log，非常劣。

事实上，只需求出每个集合 r\le y 的最大 l，然后将每个集合最大 l 取 \min，若其 \ge x 就合法。那么直接按 r 从小到大加入，拿个主席树维护即可。O(n\log n)。

不过转化和猫树套主席树的思路值得借鉴一下。

P3332 [ZJOI2013] K大数查询

题意：n 个可重集，支持将区间内集合都加入 x、查询区间内集合的并的第 K 大。n,m\le 5\times 10^4。