一些常用的数据结构维护手法
command_block
2020-02-01 17:41:22
# -1.前言
可配合 [题单:一些常用的数据结构维护手法](https://www.luogu.com.cn/training/5297) 食用。
这里讲的不是数据结构,而是数据结构的使用技巧。
如果把经典数据结构比作装备的话,这些技巧就是使用装备之前必学的技能。
当然,技能并不能直接增强武器本身,但是可以更加巧妙地分解问题。
对于每种技巧,都会有一些基本要素:
- **要求** : 什么样的数据结构可以使用这个技巧呢?
- **效果** : 使用这个技巧我们能玩什么exciting的操作呢?
- **扩展** : 这个技巧在其他奇奇怪怪的地方有什么用处呢?这个技巧有什么本质理解吗?
此外要注意的是,**不适合**在对某种算法毫无印象的时候,尝试使用本Blog入门,那会令你多走弯路。
最好是在有初步印象之后再来看,或者复习的时候看,会有比较好的效果。
题目不一定是最适合入门的(所以对综合能力要求较高),但是是比较适合总结性质的。
如果想看**浓缩版**的总结,请直接翻到每一节的末尾。
------------
# 0.常见的数据结构
先来清点一下去我们的武器。(本人孤陋寡闻如果有人知道更多请在评论区空投感激不尽qwq)
武器都有各自的特点,技能要配合合适的武器。
我们需要分析的,不仅是武器的长处,还有武器的弱点。
你可以这么认为 : 武器在拥有某种弱点的同时,必然相应地在其他方面有长处,否则早就被淘汰了(凸包?)
所以,假如你在做题的时候,发现出题人特意在某些方面放松要求,如允许离线,内存宽裕,看起来能加权却偏偏不加权等行为,你就可以按照这些特征去寻找合适的武器。
换句话说,尽量使用题目给你的全部特殊条件。
~~当然,不排除出题人懒或者题很简单的情况。~~
- 方便构造,但不方便修改(静态)
贡献可以“分体”计算,把信息(修改)分成几份,分别构造数据结构,分别查询,可以合并答案。
也就是说,不能考虑操作之间的互相影响。
一个简单的排除方法是 : 能否支持消除任个操作的影响(删除)。
- 正确的例子
- 有序序列(相对BST而言) : 有几个数$≤Lim$
- AC自动机 : 匹配次数
- 凸壳(动态可以做,只是比较麻烦) : 函数最大值
- 虚树
- 后缀数组/SAM(`parent tree`上构造)
- 错误的例子
- 大多数的图上路径问题,因为路径难免会互相影响。
- 可支持假如,撤回,但不支持删除(时间栈)
理论上,所有**非均摊**的数据结构都可以撤回。
一个显然的方法是 : 开栈记录所有的数组修改,然后反着做回去。
对于需要均摊分析复杂度的数据结构,也并非一定无法撤回,如果能够把撤回操作描述成这个数据结构的原操作的话,仍然能使用均摊分析。
举个例子 : LCT维护最小生成树。
由于每次操作时加入一条边会删去环上最大边,丢失了原图的信息,肯定是不能支持任意删除的。
但是撤回的时候,只需要把连断边操作反着做就好了。
也就是说,数据结构本身是能够删除的,但是由于做法的正确性限制无法任意删除。
- 正确的例子
- 并查集(按秩合并)
- LCT维护最小生成树
- 线性基
- 动态凸壳(虽然一次可能删掉很多点,把删去的点放到别处暂存即可)
- 错误的例子
- 大多数均摊数据结构,如果不支持删除,那就不用考虑了。
- 静态的就更不用说了。
------------
# 1.逆向思维
这并不是一个固定的算法,但可以衍生出许多套路,甚至涉及和数据结构无关的领域。
## 1.1 时间倒流
考虑某种动态问题,按着题目给出的顺序做,我们不会,但是倒过来做就会了。
于是我们倒过来做(废话)
常见的有 删除$\Leftrightarrow$插入 ;分裂$\Leftrightarrow$合并 等等。
总之,要在这个过程中找到对状态的逆操作。
- **例题** : [P1197 [JSOI2008]星球大战](https://www.luogu.com.cn/problem/P1197)
**题意** : 删边求联通块个数。
考虑删边的逆操作是加边,而加边求连通块个数就是并查集基本操作。
[评测记录](https://www.luogu.com.cn/record/17950322) (~~代码时间久远,不喜勿喷~~)
## 1.2 查询/状态的互补
找出贡献的充要条件,然后做等价变换。
- **例题①** : [P1502 窗口的星星](https://www.luogu.com.cn/problem/P1502)
**题意** : 给一个固定的平行于坐标轴的$r*c$矩形,问其最多能在平面直角坐标系中框柱几个点。
直接做并不好做,我们不知道该把这个矩形放在哪里,决策空间很大。
设矩形左上角为$A$,一个点能被统计到的充要条件 : 点在矩形内。
然而,我们如果把每个点变成以其为右下角的$r*c$矩形,其能贡献的充要条件变为 : $A$在产生的矩形内。
现在问题就变成了 : 寻找一个点使其在最多矩形内。
我们使用扫描线即可。
[评测记录](https://www.luogu.com.cn/record/18517338) (~~代码时间久远,不喜勿喷~~)
- **例题②** : [P2982 [USACO10FEB]慢下来Slowing down](https://www.luogu.com.cn/problem/P2982)
**题意** : 给出一棵树,要求支持单点加,从根到某个点的路径求和。
树链剖分可以做,但是没必要。
我们的修改十分简单,但是询问很难,我们不妨把两者的难度平衡一下。
考虑一个修改$u$会对某个询问$v$有贡献的充要条件 : $u$在$rt$到$v$的路径上。
也就等价于 : $u$是$v$的父亲,$v$在$u$的子树内。
现在就变成了 : 给出$v$统计其在多少个点的子树内。
我们每次子树加,单点查询。dfs序拍扁之后,使用序列线段树即可。
[评测记录](https://www.luogu.com.cn/record/9554392) (~~代码时间久远,不喜勿喷~~)
- 其实这东西在DP里面也有应用,先咕着
------------
# 2.CDQ分治
考虑若干个查询 $\texttt{Q}$ ,和修改 $\texttt{C}$ ,查询只会被自己前面的修改影响。
我们无法找到某种直接实现这个目的数据结构(或者常数过大,很难实现),但是我们发现,**静态**的问题十分好做。
(而且,$\texttt{C}$ 可以向 $\texttt{Q}$ 分批次贡献)
换句话说,如果 $\texttt{C}$ 全在 $\texttt{Q}$ 前面,这个问题我们就会做了,此外,初始化的复杂度和 $\texttt{C}$ 的个数相关。
那么我们**可能**可以采用这个分治方法解决问题。
- **算法流程**
我们考虑如下的操作序列 :
$\large\underline\texttt{C C Q C C Q Q C}$
1. 我们从正中间分成两半,考虑左边的修改对右边询问的贡献(**跨越隔板的贡献**),可得:
$\large\underline\texttt{C C Q C}\ \ |\ \ \underline\texttt{C Q Q C}$
$\large\underline\texttt{C C . C}\Rightarrow\underline\texttt{. Q Q .}$
我们采用我们会的**静态**方法解决这个问题。
然后因为不再需要考虑跨越隔板的贡献,相当于这两块不再有关系,可以分治成子问题。
2. 分治处理左边的$\large\underline\texttt{C C Q C}$
3. 分治处理右边的$\large\underline\texttt{C Q Q C}$
如此分治下去……
------------
- **例题①** : [P3374 【模板】树状数组 1](https://www.luogu.com.cn/problem/P3374) (~~纯属娱乐~~)
这里把区间询问容斥变成两个前缀相减,把问题转化成 :
初始全`0`的一维数组,单点加,前缀求和。
采用CDQ分治,考虑这一个子问题中有$O(m)$个操作。
考虑跨越隔板的贡献,现在是个静态问题。
$\large\underline\texttt{C C C...}\ \Rightarrow\ \underline\texttt{Q Q Q...}$
我们可以先把 $\texttt{C}$ 和 $\texttt{Q}$ 按照数组位置排序,然后就变成了一个十分显然的前缀和。
问题在于,我们还需要排序,这会让复杂度多个 $log$。
- **技巧** : 分治中归并
有些时候,我们使用 $\texttt{C}$ 建立静态结构时,直接建立复杂度较劣,但是利用两个儿子余下的信息建立,则更快一些。
比如说有序序列,直接`sort`是$O(nlogn)$的,但把两个儿子的有序序列合并是$O(n)$的。
除此之外还有凸壳(也需要排序)
此时,我们就要求先分治处理两个子问题(**后序遍历**),再计算跨越本分隔板的贡献。
现在就可以做到真正的$O(m)$了,不过感觉还是比直接“离散化+树状数组”麻烦许多……
分析复杂度的时候,注意到分治树总共有$O(logn)$层,每一层分成若干堆操作,不可能有两堆含有同一个操作。
每一层的操作总个数$O(n)$,每一堆的复杂度是$O(m)$,单层总复杂度是$O(n)$,总的复杂度$O(nlogn)$。
为了提供简易CDQ的代码,方便大家对照,我还是写一下:
~~可以看到比树状数组难写很多倍~~,这题非要严格$O(nlogn)$才行。
[代码Link](https://www.luogu.com.cn/paste/lo2wsva9) + [评测记录](https://www.luogu.com.cn/record/30219655)
------------
- **例题②** : [P3810 【模板】三维偏序（陌上花开）](https://www.luogu.com.cn/problem/P3810)
等会,你前面讲到有修改,这怎么是个静态问题啊(完了我连静态都不会做)……
- **技巧** : 偏序降维$\rightarrow$时间轴
偏序问题是一类比较常见的问题,一般来讲,对某一维**排序**作为时间轴,可以降维并转化成动态问题。
也就是说,按照第一维从小到大加入元素,那么后面的点会被前面的点贡献,就满足了偏序要求。
现在就转化成了 : 支持加点,查询前缀2D矩阵点值和。
不过注意,只有静态问题能这么做,因为你只有一个时间轴。
还有一个问题是,若果有两个点的位置相同,而且比较是 $[\leq]$ 的话,这两个点会互相贡献。
有些时候可以把重($ch\acute ong$)点缩成一个,有些时候可以提前补算**从后向前**的贡献,本题采用后者。
如果补算贡献的话,分治中的排序一定要采用**稳定排序**,可以用`stable_sort`。
每个点分别产生一次修改,一次查询。
一个容易口胡的做法是 : 树套树/2DT,但是常数过大,而且并不好写。
仍然考虑隔板左边的修改对右边询问的贡献(跨越隔板的贡献)。
现在就是静态问题了,直接使用数据结构仍然没有思路,我们考虑再一次“偏序$\rightarrow$时间轴”
将第二维排序之后,现在是个这样的问题 : 一维数组,单点加,前缀求和。
直接树状数组就好了,复杂度$O(mlogm)$,注意这里不能无脑`memset`初始化,要把上次的操作撤销来达到清空的目的。
总复杂度就是$O(nlog^2n)$,代码实现较之其他方法较为简易,常数也不大。
这里顺便提一下,在CDQ分治的时候,内层数据结构的复杂度,往往已经超过外层**直接排序**转化偏序的复杂度,此时直接排序是不会增加复杂度的。
[代码Link](https://www.luogu.com.cn/paste/dm7wdvet) + [评测记录](https://www.luogu.com.cn/record/30232913)
当然,这是使用树状数组解决二维静态数点问题,而前面讲了,CDQ分治也能做,而且复杂度为$O(mlogm)$(需要归并技巧),一样的复杂度。
[代码Link](https://www.luogu.com.cn/paste/59t6oo3d) + [评测记录](https://www.luogu.com.cn/record/30247091)
- **进阶题①** : [P4169 [Violet]天使玩偶/SJY摆棋子](https://www.luogu.com.cn/problem/P4169)
**题意** : 要求维护一个数据结构,资瓷两种操作:
- A 在$S$中加点$(x,y)$
- B 给一个观测点$A$,查询目前的$S$内,与$A$最近的曼哈顿距离($dist(A,B)=|A_x-B_x|+|A_y-B_y|$)
注意到这个绝对值比较难搞,先考虑$S$中在$A$左下方的点:
有 $B_x\leq A_x;B_y\leq A_y$ ,可得 $dist(A,B)=(A_x+A_y)-(B_x+B_y)$
点权设为 $(B_x+B_y)$ ,现在就变成了动态前缀2D矩形最大值。
(其他的情况可以旋转坐标系重做得到)
考虑CDQ变成静态问题,又可以排序变成一维动态问题 : 动态前缀最大值。
直接树状数组就做完了,是不是十分`naive`啊?
这道题比较卡常数,写个归并会快一点。
[代码Link](https://www.luogu.com.cn/paste/dt69emhm) + [评测记录](https://www.luogu.com.cn/record/30257944)
- **进阶题②** : [P3769 [CH弱省胡策R2]TATT](https://www.luogu.com.cn/problem/P3769)
首先把重点合并。
定义高维点的比较 : $[A\leq B]=[A_x\leq B_x][A_y\leq B_y]...[A_z\leq B_z]$(就是$A$每一维都小于等于$B$)
这个题目要求我们做这样的一个DP:
$dp[i]=1+\max\limits_{P_j\leq P_i}dp[j]$
我们可以把前面的$dp$值看做修改,那么修改依赖会依赖前面的询问。
我们就必须按照$P$递增的顺序来转移,保证转移时前继$DP$值已经正确,否则可能漏解。
我们还是先按照一维排序(第一维相同比第二维,再相同比第三维……),同时也按照这样的顺序转移,就能够保证不会漏解。
问题在于,现在我们的CDQ分治需要换个写法。
- **技巧** : DP转移强制中序遍历
前面的写法是先处理跨越隔板的贡献,再分治下去。
现在,我们的询问之间也有了依赖关系,必须保证前面的询问回答完,才能准确得到后面询问的贡献。
我们可以对分治树**中序遍历**,也就是说在处理完[l,mid]的所有贡献之后再处理跨越隔板的贡献,此时[l,mid]中的询问已经得到了正确结果。
不过注意,这东西和归并是不兼容的,因为归并要求后序遍历,一个补救的方法是预处理归并存下信息,不过往往会使空间多个$log$,不推荐。
~~另一个补救的方法是,不使用CDQ分治~~
一般来说这种依赖关系是会传递的,内层问题也应考虑到这一点。
现在我们少了一维,变成了动态问题 : 每次加入一个点,询问3D前缀立方体中的$\max$,修改依赖询问。
仍然不会,考虑CDQ降维,再排序,变成了 : 每次加入一个点,询问2D前缀长方体中的$\max$,修改依赖询问。
仍然不会,考虑CDQ降维,再排序,变成了 : 每次加入一个点,询问1D前缀$\max$,修改依赖询问。
这东西一个树状数组带走就好,再写CDQ反而麻烦。
总复杂度$O(nlog^3n)$,常数较小。
由于离散化写挂调试一小时,在此警示后人 : 全局变量跳跃使用一定小心。
[代码Link](https://www.luogu.com.cn/paste/fdg9dy56) + [评测记录](https://www.luogu.com.cn/record/30282659)
还有很久之前写的3次CDQ嵌套的解法,懒得修了直接丢个[评测记录](https://www.luogu.com.cn/record/25717026)算了。
有一道很类似的题目是[P4849 寻找宝藏](https://www.luogu.com.cn/problem/P4849),只不过还要顺便统计方案数。
[ CDQ嵌套+树状数组 ] : [评测记录](https://www.luogu.com.cn/record/30285665)
[ 3次CDQ嵌套 ] : [评测记录](https://www.luogu.com.cn/record/19969106)
- **进阶题③**: [CF1045G AI robots](https://www.luogu.com.cn/problem/CF1045G)
**题意** : 给出$n$个三元组${x_i,r_i,q_i}$,以及常数$K$
两个三元组$(i,j)$之间能贡献当且仅当$(x_i-x_j)\leq\min(r_i,r_j)$且$|q_i-q_j|\leq K$
问能够贡献的对数。
首先,这是个静态问题,我们需要按某种**顺序**将其变成动态问题。
经过认真的思考,容易发现让看得近的数看得远的比较合理(按视野从大到小排序)。
在所有的约束条件中,只有$|x_i-x_j|\leq\min(r_i,r_j)$中含有$\min$,这和传统的偏序问题大不相同。
如果你按照其他的顺序来数,你就会发现一个尴尬的问题 : 数到的元素不一定看得见接收者。
然而,如果按照视野为序,那么能否贡献就只跟统计者的视野有关了。我们把问题转化成了下面的样子:
动态加入三元组${x_i,r_i,q_i}$,并查询目前有的三元组中,满足$|x_i-x_j|\leq r_i$且$|q_i-q_j|\leq K$的个数。
这就是个裸的动态二维数点了,可使用与上文相同的方法解决。
注意需要容斥拆询问。这题值域很大,但是可以只在$q$的一维离散化。
由于这道题是无序对计数,写起来细节较少。
然而这题$K$相当小,貌似可以直接动态开点线段树艹过去……
[代码Link](https://www.luogu.com.cn/paste/3006hihz) + [评测记录](https://www.luogu.com.cn/record/30270934)
- **进阶题④** [CF848C Goodbye Souvenir](https://www.luogu.com.cn/problem/CF848C)
[题解Link](https://www.luogu.com.cn/blog/command-block/ds-ji-lu-cf848c-goodbye-souvenir)
- **进阶题⑤** : [P4027 [NOI2007]货币兑换](https://www.luogu.com.cn/problem/P4027)
[题解Link](https://www.luogu.com.cn/blog/command-block/dp-ji-lu-p4027-noi2007-huo-bi-yue-huan)
- **进阶题⑥** : [BZOJ2961: 共点圆](https://www.lydsy.com/JudgeOnline/problem.php?id=2961)
[题解Link](https://www.luogu.com.cn/blog/command-block/post-ji-lu-bzoj2961-gong-dian-yuan-4140-gong-dian-yuan-jia-qiang-ban-post)
- **浓缩版**:
考虑某种动态问题,静态版本($\texttt{C}$ 全在 $\texttt{Q}$ 前面)我们会做,而且复杂度只和操作次数相关。
要求可以把 $\texttt{C}$ 分批次向 $\texttt{Q}$ 贡献。
考虑每次在操作中间插一个隔板,只考虑跨越隔板的贡献,此时是静态问题,可以解决。
然后两块之间不再有关系,考虑分治。
一句话来讲 : **以静制动,必须离线**
复杂度 : $logn*$(查询) + 总大小为$O(nlogn)$的build。
- **技巧①** : 分治中归并,考虑利用两个儿子的信息,更快地建立静态结构,需要强制后序遍历。
- **技巧②** : 偏序降维$\rightarrow$时间轴,对偏序的某一维排序就变成了动态的低维问题。
- **技巧③** : 有些DP类问题修改会依赖前面的询问,此时则需要按分治树中序遍历计算贡献。
------------
# 3.线段树分治
考虑某种奇怪的动态问题,我们有查询 $\texttt{Q}$ ,加入元素 $\texttt{A}$ ,和删除元素 $\texttt{D}$ 三种操作。
但是,如果没有 $\texttt{D}$ 操作,我们就会做。
那么我们**可能**可以采用这个分治方法解决问题。
- **算法流程**
先考虑一个暴力 : 按照时间点开若干个桶,把每个元素的存在**时间段**计算出来。
然后,把 $\texttt{A}$ 操作扔进对应时间段的桶里(如果已经被删掉了,则不加入)。
对于每个桶,做一遍其中的 $\texttt{A}$ 就能得到这个时间点的正确状态。
容易发现,这个暴力是以每个 $\texttt{A}$ 多做 $O(n)$ 次的代价规避了 $\texttt{D}$ 操作。
考虑使用线段树优化这个暴力,按照时间轴建立线段树,把每个 $\texttt{A}$ 分配到对应的区间内。
我们让父节点的状态能够向儿子传递,那么只需要在$O(logn)$个点里放上 $\texttt{A}$ ,就能让在这个区间里的所有叶节点都受到这个操作的影响。
然后在线段树上$dfs$,到达每个点的时候先完成这个点所有的 $\texttt{A}$ ,然后:
向左儿子递归处理,此时左儿子自然继承了父亲的状态。
向右儿子递归处理,此时左儿子自然继承了父亲的状态。
向老爸借了东西,还的时候要纤毫不损,撤销这个点所有的 $\texttt{A}$ 对状态的影响。
至于怎么撤销,可以认为是把对所有数据的改动记录下来然后还原。
- **例题①** [Loj#121. 「离线可过」动态图连通性](https://loj.ac/problem/121)
**题意** : 支持加边删边,询问两点间连通性。
如果没有删边操作,这就是个很简单的并查集。
考虑使用线段树分治,这真就变成了很简单的并查集?
事实上,由于线段树分治会把一个状态传递给两个儿子(类似可持久化的操作树),而并不是经典的一条时间轴,所以均摊分析在线段树分治中会失效。
比如这道题如果写了路径压缩并查集,出题人可以在根节点挂一堆询问,造出一条$O(n)$的链,然后中间什么都不干。
等到叶节点,突然埋伏你一手,让你把它遍历一次,每个叶子$O(n)$总的复杂度就是$O(n^2)$,退化了。
这就需要我们使用复杂度严格(或期望)正确的算法,按秩合并并查集正符合这个要求。
至于操作怎么撤回,可以开个**栈**记录上一次让谁的父亲变为谁,然后倒着做就好了,具体见代码。
[代码Link](https://www.luogu.com.cn/paste/oyqei6qa) + [评测记录](https://loj.ac/submission/539322)
- **例题②** : [P5787 二分图 /【模板】线段树分治](https://www.luogu.com.cn/problem/P5787)
**题意** : 给出一个无向图,每条边都有一个存在时间区间,总时间为$[1,k]$,询问每个时刻该图是不是二分图。
区间就可以看做先加后删,我们先来考虑只有加入的问题。
众所周知,二分图判定的充要条件是 : 没有奇环。
关于路径的奇偶性,我们可以用带权并查集来维护。
每次加入边的时候,如果在联通块内部,查看两个点到根路径长度的奇偶性情况,如果相同,加上新边则形成奇环。
否则,计算出两个根之间的路径奇偶性,赋权并合并。
接下来套用线段树分治即可,注意采用按秩合并。
注意到如果已经形成了奇环,则当前时间区间内就都不可能是二分图了,才做直接跳过即可,可以减小常数。
复杂度$O(nlog^2n)$, [代码Link](https://www.luogu.com.cn/paste/58um0hgt) + [评测记录](https://www.luogu.com.cn/record/32177260)
- **例题③** : [P4585 [FJOI2015]火星商店问题](https://www.luogu.com.cn/problem/P4585)
**题意** : 有一排$n$个商店,某个商店会在某个时刻购入权值为$v$的商品。
有若干个顾客,各有一个参数$x$
询问在$[l,r]$商店内购买进货时间在$[tl,tr]$的商品中,$v\ {\bf xor}\ x$的最大值。
顾客和进货操作的总量不超过$m$,有$n,m\leq 10^5$,时限$\texttt{2s}$.
这题特殊之处在于,商品(修改)在时间轴上是一个点,而询问是一个区间。
采用**逆向思维**,把询问分到线段树上去,然后把商品拿来分治。
将每个商品挂到从根到叶子的点上,这样每个点就会有自己区间内的所有商品,拆区间回答询问即可。
在每个节点处,使商品根据商店位置有序,建立可持久化`01Trie`,就能够查询区间内的`xormax`.
( 至于怎么查询,可见 [P4735 最大异或和](https://www.luogu.com.cn/problem/P4735) )
这时,由于$\max$可以**分体贡献**,我们把挂着的所有询问都拉出来贡献一次即可。
复杂度$O(nlog^2n)$, [代码Link]() + [评测记录]() (准备重写)
- **进阶题①** : [CF576E Painting Edges](https://www.luogu.com.cn/problem/CF576E)
对于不同颜色的边可以开多个加权并查集。
这道题的特殊之处在于,无法预知每个修改操作是否执行,也就无法得到每条边的存在区间。
对于一个状态不变的区间,我们分成多段往线段树上挂,显然也不影响正确性。
现在修改操作可以理解为 : 有一个改变颜色的机遇,但是不知道是否会改变。
那么我们把每两个可能的改变操作之间都分段,也无伤大雅。
可以先在同一条边的两个修改之间挂上当前状态,到达询问之后判断是否合法,然后把下一个修改挂上去。
[评测记录](https://www.luogu.com.cn/record/26907938)
- **进阶题②** : [CF603E Pastoral Oddities](https://www.luogu.com.cn/problem/CF603E)
首先有一个结论 : 某个图合法当且仅当所有连通块的大小都是偶数。和本文无关就不再赘述。
我们能够发现,两个块合并,一定不会让奇数的块增多,所以我们加边**多多益善**。
容易想到的方法是`kruskal`,把边从小到大排序,依次加入,直到合法为止。
现在我们要资瓷动态加边,我们想象一条边什么时候会在决策集合里面 : 加入的时候很优,进入了决策集合,后来随着新边加入被抛弃。
据此容易发现,每条边存在与决策集合中的时间是一个区间。
这让我们看到了线段树分治的希望,可是怎么求出这个区间呢?
考虑从后往前做暴力,显然,每条边第一次加入的时刻就是其区间的末尾。
- **技巧** : 当操作的状态或者时间区间不确定的时候,可以按某种顺序分治以恰好得到信息
比如上一题,就必须按照从左到右的顺序分治,以从前面的询问得到后面的颜色信息。
更毒瘤的是,本题连时间区间都未知。不过这个区间的左端点我们是知道的。
考虑反过来分治(时间倒流),先递归右儿子,在叶节点处,我们得到目前半成品图的最大边权$w$
把所有剩余的边权大于$w$的边尝试加入,对于那些加进去的边,就能得到其存在区间的末尾。
一旦已满足条件就不加了,由于多多益善,中间是不会无故丢掉某条边的,所以每条边只会被考虑一次。
(坑)
------------
# 4.整体二分
考虑某种奇怪的问题,询问满足单调性,可以二分。
但是不同的$mid$需要不同的状态来判定,暴力做代价过高。
这时往往要使用整体二分来一起计算。视情况可以带修。
- **算法流程**
考虑对应的答案区间$[L,R]$,取其中点$mid=\lfloor\frac{L+R}{2}\rfloor$
我们把数据结构的状态调整到$mid$处,然后就可以判定这些询问是大于还是小于$mid$.
然后把询问分到$[L,mid]$和$(mid,R]$中去。
注意到,$mid$的移动总量是$O(nlogn)$的,每个询问判定的次数是$O(logn)$的。
实质上就是最大化询问的共用判定。
------------
- **例题①** : [P1527 [国家集训队]矩阵乘法](https://www.luogu.com.cn/problem/P1527)
**题意** : 给定一个$N\times N$的矩阵,多次询问一个子矩形的第$K$小数。
$N\leq 600;q\leq 60000$ ,时限$\texttt{1.5s}$
先将矩阵内的数字离散化并排序。
分治到$[L,R]$时,将不超过$mid$的数字全部加入二维树状数组(单点`+1`)
根据上一次的状态加或者删数字。$mid$的总变化量是$O(n^2logn)$的,这部分的复杂度就是$O(n^2log^3n)$
然后判定就是矩阵查询,和$K$比较。这部分复杂度是$O(qlog^3n)$
由于每个数对单个询问的贡献方式固定,还有另一种写法 :
考虑类似线段树二分,我们进入右子树时会抛弃左子树的信息。
我们把矩阵中的数字带着一起分治,分治到$[L,R]$时,我们只加入$[L,mid]$的数字,然后判定。
如果$K$大于查询值$c$,则减去$c$,分配到右区间,这样就和大小在左区间的数无关了。
注意判定完毕之后要清空树状数组。
复杂度依然是$O((n^2+q)log^3n)$,常数较小。
一开始挂了几发,对着代码看了半小时啥也没看出来很自闭,后来拍了才发现是数组开小了……
[代码Link](https://www.luogu.com.cn/paste/p3n39z73) + [评测记录](https://www.luogu.com.cn/record/31651595)
------------
- **例题②** :[P4175 [CTSC2008]网络管理](https://www.luogu.org/problemnew/show/P4175)
**题意** : 给定一棵树,有点权,单点修改和询问路径第$K$小数。
区别在于,这题多了修改。
事实上,我们可以根据时间轴来分析 : 前面的修改能影响后面的询问。
我们在整体二分的时候,把修改也根据权值传下去,同时保证询问和修改的相对顺序不变。
注意要把修改拆分成删除和添加,这两部分可能被分到不同的区间里去。
我们需要树上单点修和路径求和,考虑采用`LCT`或者树剖。
- **技巧** : 带修整体二分
如果修改可以向询问分体贡献(类比`CDQ`),贡献容易合并,我们就可以把修改带着一并二分。
注意,题目中原有的修改可能会在二分的意义下有变化。比如赋值$\rightarrow$删除&加入。
[代码Link](https://www.luogu.com.cn/paste/q1w8bzdj) + [评测记录](https://www.luogu.com.cn/record/31682760)
------------
- **进阶题①** [P3527 [POI2011]MET-Meteors](https://www.luogu.com.cn/problem/P3527)
**题意** : 给一个序列,多次区间加正数,询问每个位置达到$lim[i]$所等待的操作数。
对时间轴二分即可。要采用带修整体二分的思想,将已经贡献过的操作减去。
[提交记录](https://www.luogu.com.cn/record/31690389)
- **进阶题②** [CFgym102354B. Yet Another Convolution](https://codeforces.com/gym/102354/problem/B)
[题解Link](https://www.luogu.com.cn/blog/command-block/post-shuo-lun-ji-lu-cfgym102354b-yet-another-convolution)
- **进阶题③** [P5163 WD与地图](https://www.luogu.com.cn/problem/P5163)
[题解Link](https://www.luogu.com.cn/blog/command-block/ds-ji-lu-p5163-wd-yu-di-tu)
# 5.猫树分治
考虑某种奇怪的**序列**静态问题,我们并不会做。
但是,如果所有询问的区间有交集,那么我们就能通过下列算法得出答案。
选取所有询问都包含的某个位置,分别向左向右预处理某些东西。
对于询问的回答,只需要在左端点取信息,在右端点取信息,再组合即可。这要求(答案/状态)能够合并。
然后我们套用猫树分治,就能够处理更一般的情况了。
此外,将分治树存下来,往往就能够做到强制在线。
- **算法流程**
考虑一堆询问区间和对应的状态区间$[L,R]$。
我们取状态区间的中点$mid=\lfloor\frac{L+R}{2}\rfloor$,从$mid$分别向左右预处理某些信息。
遍历所有询问,如果跨过$(mid,mid+1)$,则合并左右端点信息来回答。
如果在$[L,mid]$中,则下放到左儿子。
如果在$[mid+1,R]$中,则下放到右儿子。
继续分治。
(不难发现其实就是序列上的点/边分治,所以上猫树的题目可能可以上点/边分树)
------------
- **例题①** : [P6240 好吃的题目](https://www.luogu.com.cn/problem/P6240)
- **例题②** : [CF1100F Ivan and Burgers](https://www.luogu.com.cn/problem/CF1100F)
**前置芝士** : 线性基,向其中插入的复杂度是$O(\log c)$的,合并两个线性基是$O(\log^2c)$的.
有一个显然的暴力 : 建立线段树,暴力合并$O(\log n)$个线性基,复杂度$O(n\log n\log c+q\log n\log^2c)$,
考虑如果所有区间都包含$mid$,我们从$mid$向左向右扩展,每个询问只需要合并左右端点的两个线性基即可。
套用猫树分治,额外的代价仅为$O(q\log n)$,总复杂度为$O(n\log n\log c+q(\log n+\log^2c
))$
(坑)
- **进阶题①** : [P5576 [CmdOI2019]口头禅](https://www.luogu.com.cn/problem/P5576)
需要SAM技巧,慎入,[题解Link](https://www.luogu.com.cn/blog/command-block/solution-p5576)
- **进阶题②** : [P6109 [Ynoi2009]rprmq](https://www.luogu.com.cn/problem/P6109)
需要线段树技巧,慎入,[题解Link](https://www.luogu.com.cn/blog/command-block/ds-ji-lu-p6109-ynoi2009rprmq)
------------
# 6.二进制分组
还是考虑某个动态问题,静态版本($\texttt{C}$ 全在 $\texttt{Q}$ 前面)我们会做,而且复杂度只和操作次数相关。
还要满足可以把 $\texttt{C}$ 分批次向 $\texttt{Q}$ 贡献。
有没有发现这个要求和“CDQ分治”一样啊?
奇妙的是,这种方法往往是能够做到在线的。所以这在效果上就是CDQ的强化版。
实现方法多种多样,不特别讲,在下方例题就可以看见了。
- **例题①** : [CF710F String Set Queries](https://www.luogu.com.cn/problem/CF710F)
**题意** :
- 支持向集合$S$中加,删字符串。
- 给出文本串$T$,询问$S$中所有串出现的总次数。
强制在线。
加和删本质是同种操作,删可以看成贡献为$-1$.
先考虑**静态**的问题怎么做。
对 $S$ 建立AC自动机,在 $Fail$ 树上下传串个数,把匹配到每个节点能获得的匹配次数求出。
然后对于询问,暴力跳自动机求和即可。
现在考虑在线。
我们新加入一个串的时候,不能直接修改现有的AC自动机,又不能重新建造。
如果我们现在有若干个AC自动机瓜分 $S$ ,我们将 $T$ 在每个串上都跑一次即可。
我们可以采用如下的方法来维护这一群AC自动机 :
- **写法①** : jiry : 2048
加入新串时,查看上一个AC自动机中的**串数**是否与自己相等,如果相等则合并,不断重复这个过程。
实际上写代码的时候,可以一口气找到合并的结束位置,然后一口气合并,可以减小常数。
目前存留的AC机个数,就相当于串数的二进制表示中 $1$ 的个数,为 $O(logn)$
如果一个串待在大小$2^i$的AC机里,就说明他被合并了 $i$ 次,而 $n$ 个串最多合出 $2^{logn}$ ,每个串被合并的次数也就是 $O(logn)$。
这道题不使用这种方法实现,因为下一种写法更方便。
- **写法②** : 替罪均摊
加入新串时,查看上一个AC自动机中的**串总长**是否小于自己的$\alpha$倍。
如果是,则将两堆合并。
由于每一个AC机总串长都会比上一个至少减小$\alpha$倍,所以总个数就是$O(log_{\alpha}L)$的。
重构的复杂度考虑均摊证明,分层考虑势能。
加入新串时,在当前层增加了$len$的势能(串长)。
合并时,设本层势能为$h$,则消耗的时间为$\Theta((1+\alpha)h)$。合并后,本层势能转移到上一层。
考虑到势能最多会上升$O(log_{\alpha}L)$层,而势能与时间之间的兑换是 $1:(1+\alpha)$ 的,所以重构总复杂度为$O((1+\alpha)Llog_{\alpha}L)$
实际上可以微调$\alpha$来实现常数平衡,常取$\alpha=2$。
[代码Link](https://www.luogu.com.cn/paste/340cc8qp)
- **例题②** : [P3309 [SDOI2014]向量集](https://www.luogu.com.cn/problem/P3309)
考虑给定的 $(x,y)$ 与集合中 $(a,b)$ 点积的式子 : $ax+by=y(a·\frac{x}{y}+b)$
相当于我们在维护若干条 $y=ax+b$ 的直线,每次代入 $\frac{x}{y}$ 当做 $x$ 求所有直线的值的 $\max$.
现在问题就变成了 :
- `push_back`一条直线。
- 查询某个区间的直线在 $x=c$ 时的最大取值。
先考虑静态问题怎么做:
建立线段树,每个节点 $[l,r]$ 上是向量 $[L_l,L_r]$ 形成的凸包。
构造凸包需要排序+单队,使用归并可以省掉排序的$log$,构造这么一个线段树的复杂度是$O(nlogn)$。由于不是每条线段都会在凸壳上,实际常数较小。
现在考虑使用二进制分组来解决,此时使用外层线段树的写法公认比较简洁。
外层写一个线段树,加入直线就是单点修。
假如两个儿子都**满了**,则把自己的凸包build起来。
查询的时候直接在线段树上拆分区间+凸包二分即可(常数较小)。
复杂度$O(n\log^2n)$,这题比较卡常数,建议归并建立凸包。
[代码Link](https://www.luogu.com.cn/paste/cxdeh6em)
- **例题③** : [Uoj#191. 【集训队互测2016】Unknown](https://uoj.ac/problem/191)b
考虑给定的 $(x,y)$ 与集合中 $(a,b)$ 叉积的式子 : $bx-ay=x(-a·\frac{y}{x}+b)$ ，仍然是一次函数问题。
和上一题主要的区别在于，支持在末尾的删除操作。
若某个线段树节点包含有一个被删除的向量，则直接报废。
如果还采用旧的策略，一次删除可能破坏掉一个大块，复杂度退化。
解决办法 ： 在这个区间刚满的时候不 $build $这个区间，等到同层的下一个区间也填满的时候再 $build$ 这个区间。
这样，显然每层只有至多 $2$ 个未 $build$ 的区间，查询复杂度仍然可以保证。
删除时，要越过后一个整个区间才能破坏前面已经被 $build$ 的区间，复杂度仍然均摊正确。