专栏文章

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

__Cheems
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioslio9
此快照首次捕获于
2025/12/03 00:28
3 个月前
此快照最后确认于
2025/12/03 00:28
3 个月前
查看原文
By fishpear。远古大神，讲得好啊。

可持久化数据结构

首先是主席树，耳熟能详了属于是，考虑推广一下：
  • 假如我们的数据结构是个树且不存储父节点，就能套用主席树的方法。
众所周知，平衡树难以可持久化。主要原因在于旋转操作依赖于父节点，但其实可以在递归过程中存储祖先链到一个数组，就能做到可持久化。当然没人写这玩意。
同时课件指出：fhq treap 本质上是将上述数组用递归时的系统栈存起来，也就是说两种方法是相同的。
然后是区间修改，一般来说我们得写标记永久化，但是真的不能用标记下传了吗？不是的。
最后，对于一般的数据结构也能可持久化吗？可以的，用可持久化数组即可，例子是并查集。不过会多一只 log。
同时，假如只要求回滚，拿个栈存储修改即可。
对于特定问题，存在不带 log 做法。视频链接，当然这玩意不考。

P2839 middle

经典套路：中位数无脑二分答案 midmid。
将 ≤mid\le mid 设为 11，>mid>mid 设为 −1-1。那么区间中位数 ≥mid\ge mid 等价于区间和 >0>0。所以问题变为寻找最大区间和，这是容易的。然后用主席树存下每个 midmid 的线段树即可。O(nlog⁡2n)O(n\log^2n)。
由此提出运用可持久化的基本方法：若发现将询问离线后数据结构可解，将该数据结构可持久化便能在线了。也就是说，可持久化具有强制转在线的作用。

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

题意：无向图，多次询问从 s→ts\to t，变身前只能在 [l,n][l,n]，变身后只能在 [1,r][1,r]，问是否可行。
枚举变身点，问题转化为 ss 只走 [l,n][l,n]、tt 只走 [1,r][1,r] 两个连通块是否存在交集。
联想到 kruskal 重构树，分别从前往后、从后往前加入点，那么两个连通块对应两个森林上的两个子树。使用 dfs 序刻画限制，将点转化为二维数点，坐标分别是两个森林上的 dfs 序，每次询问一个矩形是否有点，主席树即可。
这题重点在于用 kruskal 重构树将连通块转化为子树、并通过 dfs 序转化为二维数点问题。主席树只是工具。
细节：kruskal 重构树按点权构建，只需将边权设为两端点编号最值即可。

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

题意：一棵 n+1n+1 层的树，每一层恰有一个点有两个儿子，其它只有一个，编号从上到下、从左往右。多次询问求 lca(x,y)lca(x,y)。
直观想法是倍增跳 lca，问题变为对任意点求任意级祖先。为了解决这个问题，重新编号以观察性质：
从下往上，考虑每个叶子对应该层的哪个点，可以发现，是前缀 [1,p][1,p] 编号不变，后缀 (p,n](p,n] 编号减一。想到用主席树后缀减、单点查。但是点不一定是叶子，需要找到其子树内一个叶子，需支持寻找 xx 对应下标，由于序列有序，树上二分即可。
突破点在于观察到相邻层之间节点编号变化的规律，并联想到运用主席树维护叶子每层对应祖先、以支持倍增。

QOJ970 Best Subsequence（无代码，要补）

题意：给一个数组，多次询问在 [l,r][l,r] 中选 kk 个数，最小化相邻数之和（包括首尾）的最大值。
较为困难的一题。
二分答案 limlim 转判定。然后有一个套路：将 ≤lim2\le \frac {lim}2 的视为 00、>lim2>\frac {lim}2 的视为 11。那么 0000 一定行，1111 一定不行，0101 看情况。
贪心地想，先全选 00 肯定不劣。直觉上很对。考虑最优解存在一个 00 不被选，若加入后产生 0101 非法，那么将这个唯一存在的 11 去掉即可。
接下来加入 11，对于首尾和相邻 00 之间的 11 显然取最小的，判断能否加入即可。
考虑用数据结构加速这个过程，考虑 limlim 从小到大，每次修改 11 变成 00。考虑相邻 00 构成的段，那么总共会有 O(n)O(n) 次区间分裂，对于不分裂的区间，会在某个时间由不可选变为可选，拿一个线段树捕捉这些点即可。对于分裂的区间，我们直接取出最小值并标记是否可选即可。
然后用主席树维护即可，O(nlog⁡2n)O(n\log^2 n)。
这题主要是想到按 lim2\frac {lim}2 分类，然后贪心，并用数据结构进行优化，用可持久化支持二分。

分块

技巧性很强，见例题。

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

题意：求区间逆序对，强制在线，n,q≤105n,q\le 10^5。
大力分块取块长 n\sqrt n。
考虑整块与整块，提前排序每次做归并，预处理整块两两间的逆序对数，O(nn)O(n\sqrt n)。
考虑散块内部，必然是前后缀，用插排即可，O(nn)O(n\sqrt n)。
考虑散块与整块，相当于求一个数与一个整块，只需在整块与整块部分记录即可。查询 O(n)O(\sqrt n)。
考虑散块与散块，从整块排序结果中，提取散块排序后的结果，然后直接归并，查询 O(n)O(\sqrt n)。
考虑短区间 [l,r][l,r] 在整块 [L,R][L,R] 中，考虑容斥，可以直接提取出 [L,l),[l,r],(r,R][L,l),[l,r],(r,R] 三部分排序后结果，然后归并即可算出三部分互相的逆序对数。单次也是 O(n)O(\sqrt n)。
总的就是优美的 O(nn)O(n\sqrt n)。
这题揭示了分块的基本方法：整块、散块分开讨论。分块一般带 log 是好做的，若要去 log 则需精细实现，技巧性非常强。

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

题意：nn 个数初始为 sis_i，每秒增长 rir_i，上限为 mim_i。需支持：时间增长 tt；求区间和并马上清空区间。n,q,V≤105n,q,V\le 10^5。
可以基于颜色段 O(nlog⁡2n)O(n\log^2 n)，不讨论。
分块，将被不完全推平的段称为特殊段，初始时均为特殊段。散块暴力计算即可。
每次推平时，对特殊段进行暴力计算，并对新产生的特殊段暴力更新。那么特殊段总数为 O(q)O(q)，且除首尾外特殊段被计算后不再特殊，那么特殊段部分是 O(nB)O(nB) 的。
对于非特殊段，只需记录最晚推平时间，那么问题相当于求 ∑min⁡(t×ri,mi)\sum \min(t\times r_i,m_i)，可以按填满时间进行二分但是多个 log，由于值域较小其实可以暴力预处理出每个 tt 的答案。O(nBV)O(\frac nBV)。
取 BB 为 n\sqrt n 即可。
这题注意到被完全推平的段好做，而不完全推平的段可以暴力做，通过势能分析得到正确复杂度。

CF1129D Isolation（无代码，要补）

题意：求序列划分方案数，要求每一段恰好出现过一次的数的个数 ≤k\le k。n,k≤105n,k\le 10^5。
显然 dp，那么问题为移动右端点、快速查询合法左端点的 dp 值的总和。
数字相对独立，考虑一个数 xx，它将序列划分为若干段，那么当右端点在一个区间时合法左端点也在一个对应区间，这样的区间是 cntxcnt_x 个的。总共是 O(n)O(n) 的。
将这些区间离线下来扫描线，问题变为：区间 +1,−1+1,-1，求 ≤k\le k 位置的 dp 值的总和。询问难以用线段树维护。
尝试分块，记块长为 BB。
注意到对于整块的修改，若一开始对它进行排序并将相同的值相加起来，那只需用一个指针记录合法的前缀，修改只需左右移动指针。这启示我们维护整块有序。
考虑修改，对于散块，暴力重构排序并前缀和。由于本来整块有序，那么修改后得到几个有序序列，将它们归并即可，这样没有 log。对于整块做刚刚的操作即可。
考虑查询，对于整块，因为已经记录了指针可以直接得到答案。对于散块，暴力查询即可。
对于短区间，暴力即可。那么总复杂度是 O(nn)O(n\sqrt n)。
这题是分块优化 dp，首先要想到数字贡献独立，将“恰好出现一次”转化为 O(n)O(n) 个区间的限制。然后得到一个数据结构问题，需要想到维护整块有序方能解决。

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

题意：在无向图上支持：修改边权、只走 ≥y\ge y 的边求 xx 连通块的大小。n≤5×104,m,q≤105n\le 5\times 10^4,m,q\le 10^5。可以离线。
显然 kruskal 重构树，假如无修改就很好做了，但是有修改只能暴力重构 kruskal 树。这时要想到套路：对时间序列（操作序列）分块。它的用处是减少重构次数。
分块后，一起处理一个整块的所有询问。对于该块内未修改的边，我们可以将边权排序后跑 kruskal，由于本题可以离线，将询问挂在 yy 上便能得到每个询问对应的连通性。然后暴力补上被修改的边，最后使用回滚操作把这些边撤销即可。
取块长 q\sqrt q，O(mqlog⁡m+qqlog⁡n)O(m\sqrt q \log m+q\sqrt q\log n)。
本题是可撤销并查集与时间序列分块的结合。

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

题意：有数组 a,b,ca,b,c，需支持：单点修改 aa、询问有多少个三元组 i<j<ki<j<k 满足 bai=aj=cakb_{a_i}=a_j=c_{a_k}。n≤2×105,m≤5×104n\le 2\times 10^5,m\le 5\times 10^4。
查询的形式实在是太怪了，不妨令 bi←baib_i\gets b_{a_i}，ci←caic_i\gets c_{a_i}，那么问题变为单点改 a,b,ca,b,c，查询 bi=aj=ckb_i=a_j=c_k。
然后每个数字贡献独立，所以单独考虑。那么显然有 dp，记 fi,jf_{i,j} 考虑前 ii 位且取了 jj 个数字的方案。转移容易。
发现可以根号分治！对于出现次数（原序列次数加操作次数）小于 BB 的，直接暴力计算 O(B)O(B)。然后考虑查询，相当于总共有 O((n+m)B)O((n+m)B) 次单点改和 O(m)O(m) 次前缀求和，根号一体两面一下 O(1)O(1) 改、O(B)O(B) 查，总的就是 O((n+m)B)O((n+m)B) 的。
对于出现次数 >B>B 的只有 O((n+m)B)O(\frac {(n+m)}B) 个，注意到 dp 可以用 ddp 的方式维护，注意这样就只能每种数字分别计算然后加起来了。转化为 O(n+m)O(n+m) 次单点改、O((n+m)B)O((n+m)B) 次前缀积，依旧一体两面，总共 O((n+m)B)O((n+m)B)。具体来说，考虑修改对后面带来的影响即可。
令 B=n+mB=\sqrt {n+m} 则 O((n+m)(n+m))O((n+m)\sqrt (n+m))。
本题需先转化三元组的形式，然后观察到数字独立并使用根号分治，同时分块带来的查询修改往往是 O(nn)O(n\sqrt n) 的，需要灵活运用一体两面以平衡复杂度。

CF1491H Yuezheng Ling and Dynamic Tree

题意：以 fai<ifa_i<i 的形式给一棵树，支持 fafa 区间减（最多减到 11）、求 lca(x,y)lca(x,y)。n,q≤105n,q\le 10^5。
容易联想到弹飞绵羊，将序列分为 n\sqrt n 块，维护每个点第一次跳出整块到达的点。那么便能方便得求出 lca(x,y)lca(x,y)，假如 x,yx,y 不在同一块就让靠后的点跳出块；否则，lca(x,y)lca(x,y) 在块内当且仅当 x,yx,y 跳出块到达的点相同，此时暴力跳即可。假如我们能 O(1)O(1) 跳出块，就能 O(n)O(\sqrt n) 回答询问。
考虑怎么修改，对于散块暴力重构。注意到 fafa 只减不增，所以对于一个整块其操作次数 ≥n\ge \sqrt n 时一步就跳出，打个标记即可；否则就暴力重构。
总共 O((n+q)n)O((n+q)\sqrt n)。
这题主要是联想到弹飞绵羊，然后观察到 fafa 不增的性质来优化修改。

树套树

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

CF1080F Katya and Segments Sets

题意：给你 nn 个集合，集合元素是区间。mm 次询问集合 sl…srs_l\dots s_r 是否均存在一个区间为 [x,y][x,y] 的子区间。n,m≤105n,m\le 10^5。
套路：区间转二维数点。那么 AA 包含 BB 等价于 AA 在 BB 左上角。
考虑一个集合，那么合法的 [x,y][x,y] 构成一个上阶梯型，问题相当于判断 sl…srs_l\dots s_r 的阶梯的交是否包含 [x,y][x,y]。
考虑怎么暴力做，将数点视为序列、其纵坐标为元素值，那么就是每个位置分别取 max⁡\max，然后看看 axa_x 是否 ≤y\le y。
套路：若区间询问复杂，但前后缀询问容易，考虑猫树分治。本质上是将询问区间放在线段树上，则必然存在一个区间包含它且它跨过 midmid，也就是能拆为前后缀的形式。
本题可以分别判定前后缀。对于这个问题，每次新增一个集合时相当于做 ∣s∣|s| 次区间取 max⁡\max，由于有序可以转为区间推平，势能分析可得复杂度正确。强制在线所以要用主席树。这个做法相当于线段树套主席树，时空间都是两个 log，非常劣。
事实上，只需求出每个集合 r≤yr\le y 的最大 ll，然后将每个集合最大 ll 取 min⁡\min，若其 ≥x\ge x 就合法。那么直接按 rr 从小到大加入，拿个主席树维护即可。O(nlog⁡n)O(n\log n)。
不过转化和猫树套主席树的思路值得借鉴一下。

P3332 [ZJOI2013] K大数查询

题意：nn 个可重集，支持将区间内集合都加入 xx、查询区间内集合的并的第 KK 大。n,m≤5×104n,m\le 5\times 10^4。
ii 集合的数 xx 视为点 (i,x)(i,x)，转化为二维数点。修改相当于一条线段都增加一个点，查询二分答案后相当于矩阵求和。树状数组套线段树即可。

P2086 [NOI2012] 魔幻棋盘

题意：n×mn\times m 的网格，支持区间加、查询区间 gcd⁡\gcd，保证查询区间包含定点 (x,y)(x,y)。nm≤5×105,q≤105nm\le 5\times 10^5,q\le 10^5。
由于 gcd⁡(a,b)=gcd⁡(a,b−a)\gcd(a,b)=\gcd(a,b-a)，所以做一次差分后 gcd⁡\gcd 不变，这样便解决了一维的问题。
对于二维的情况，考虑利用 (x,y)(x,y)，将棋盘中心设为 (x,y)(x,y)，分割为四个象限和四条轴分别求答案。每个象限 x,yx,y 分别做一次差分，差分方向取决于到 (x,y)(x,y) 方向。
那么变成了单点改、矩阵求 gcd⁡\gcd，树套树！

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...