一些常用的数据结构维护手法

command_block

2020-02-01 17:41:22

Personal

-1.前言

可配合 题单:一些常用的数据结构维护手法 食用。

这里讲的不是数据结构,而是数据结构的使用技巧。

如果把经典数据结构比作装备的话,这些技巧就是使用装备之前必学的技能。

当然,技能并不能直接增强武器本身,但是可以更加巧妙地分解问题。

对于每种技巧,都会有一些基本要素:

此外要注意的是,不适合在对某种算法毫无印象的时候,尝试使用本Blog入门,那会令你多走弯路。

最好是在有初步印象之后再来看,或者复习的时候看,会有比较好的效果。

题目不一定是最适合入门的(所以对综合能力要求较高),但是是比较适合总结性质的。

如果想看浓缩版的总结,请直接翻到每一节的末尾。

0.常见的数据结构

先来清点一下去我们的武器。(本人孤陋寡闻如果有人知道更多请在评论区空投感激不尽qwq)

武器都有各自的特点,技能要配合合适的武器。

我们需要分析的,不仅是武器的长处,还有武器的弱点。

你可以这么认为 : 武器在拥有某种弱点的同时,必然相应地在其他方面有长处,否则早就被淘汰了(凸包?)

所以,假如你在做题的时候,发现出题人特意在某些方面放松要求,如允许离线,内存宽裕,看起来能加权却偏偏不加权等行为,你就可以按照这些特征去寻找合适的武器。

换句话说,尽量使用题目给你的全部特殊条件。

当然,不排除出题人懒或者题很简单的情况。

1.逆向思维

这并不是一个固定的算法,但可以衍生出许多套路,甚至涉及和数据结构无关的领域。

1.1 时间倒流

考虑某种动态问题,按着题目给出的顺序做,我们不会,但是倒过来做就会了。

于是我们倒过来做(废话)

常见的有 删除\Leftrightarrow插入 ;分裂\Leftrightarrow合并 等等。

总之,要在这个过程中找到对状态的逆操作。

考虑删边的逆操作是加边,而加边求连通块个数就是并查集基本操作。

评测记录 (代码时间久远,不喜勿喷)

1.2 查询/状态的互补

找出贡献的充要条件,然后做等价变换。

直接做并不好做,我们不知道该把这个矩形放在哪里,决策空间很大。

设矩形左上角为A,一个点能被统计到的充要条件 : 点在矩形内。

然而,我们如果把每个点变成以其为右下角的r*c矩形,其能贡献的充要条件变为 : A在产生的矩形内。

现在问题就变成了 : 寻找一个点使其在最多矩形内。

我们使用扫描线即可。

评测记录 (代码时间久远,不喜勿喷)

树链剖分可以做,但是没必要。

我们的修改十分简单,但是询问很难,我们不妨把两者的难度平衡一下。

考虑一个修改u会对某个询问v有贡献的充要条件 : u在rt到v的路径上。

也就等价于 : u是v的父亲,v在u的子树内。

现在就变成了 : 给出v统计其在多少个点的子树内。

我们每次子树加,单点查询。dfs序拍扁之后,使用序列线段树即可。

评测记录 (代码时间久远,不喜勿喷)

2.CDQ分治

考虑若干个查询 \texttt{Q} ,和修改 \texttt{C} ,查询只会被自己前面的修改影响。

我们无法找到某种直接实现这个目的数据结构(或者常数过大,很难实现),但是我们发现,静态的问题十分好做。

(而且,\texttt{C} 可以向 \texttt{Q} 分批次贡献)

换句话说,如果 \texttt{C} 全在 \texttt{Q} 前面,这个问题我们就会做了,此外,初始化的复杂度和 \texttt{C} 的个数相关。

那么我们可能可以采用这个分治方法解决问题。

考虑如下操作序列

\texttt{C C Q C C Q Q C}

将序列均分成两半，考虑左侧修改对右侧询问的贡献（跨越隔板的贡献），这是一个静态问题

\begin{aligned} &\texttt{C C Q C | C Q Q C}\\ &\texttt{C C \_ C | \_ Q Q \_} \end{aligned}

此后，我们不需要再考虑跨越隔板的贡献，可以分治成子问题。继续处理左边的 \texttt{C C Q C}、右边的 \texttt{C Q Q C} 即可。

若原问题的总规模（操作个数）为 m，分治转化后，静态问题的总规模是 O(m\log m)。

这里把区间询问容斥变成两个前缀相减,把问题转化成 :

初始全0的一维数组,单点加,前缀求和。

采用CDQ分治,考虑这一个子问题中有O(m)个操作。

考虑跨越隔板的贡献,现在是个静态问题。

\large\underline\texttt{C C C...}\ \Rightarrow\ \underline\texttt{Q Q Q...}

我们可以先把 \texttt{C} 和 \texttt{Q} 按照数组位置排序,然后就变成了一个十分显然的前缀和。

问题在于,我们还需要排序,这会让复杂度多个 log。

现在就可以做到真正的O(m)了,不过感觉还是比直接“离散化+树状数组”麻烦许多……

分析复杂度的时候,注意到分治树总共有O(logn)层,每一层分成若干堆操作,不可能有两堆含有同一个操作。

每一层的操作总个数O(n),每一堆的复杂度是O(m),单层总复杂度是O(n),总的复杂度O(nlogn)。

为了提供简易CDQ的代码,方便大家对照,我还是写一下:

可以看到比树状数组难写很多倍,这题非要严格O(nlogn)才行。

代码Link + 评测记录

等会,你前面讲到有修改,这怎么是个静态问题啊(完了我连静态都不会做)……

每个点分别产生一次修改,一次查询。

一个容易口胡的做法是 : 树套树/2DT,但是常数过大,而且并不好写。

仍然考虑隔板左边的修改对右边询问的贡献(跨越隔板的贡献)。

现在就是静态问题了,直接使用数据结构仍然没有思路,我们考虑再一次“偏序\rightarrow时间轴”

将第二维排序之后,现在是个这样的问题 : 一维数组,单点加,前缀求和。

直接树状数组就好了,复杂度O(mlogm),注意这里不能无脑memset初始化,要把上次的操作撤销来达到清空的目的。

总复杂度就是O(nlog^2n),代码实现较之其他方法较为简易,常数也不大。

这里顺便提一下,在CDQ分治的时候,内层数据结构的复杂度,往往已经超过外层直接排序转化偏序的复杂度,此时直接排序是不会增加复杂度的。

代码Link + 评测记录

当然,这是使用树状数组解决二维静态数点问题,而前面讲了,CDQ分治也能做,而且复杂度为O(mlogm)(需要归并技巧),一样的复杂度。

代码Link + 评测记录

注意到这个绝对值比较难搞,先考虑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 + 评测记录

首先把重点合并。

定义高维点的比较 : [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分治需要换个写法。

现在我们少了一维,变成了动态问题 : 每次加入一个点,询问3D前缀立方体中的\max,修改依赖询问。

仍然不会,考虑CDQ降维,再排序,变成了 : 每次加入一个点,询问2D前缀长方体中的\max,修改依赖询问。

仍然不会,考虑CDQ降维,再排序,变成了 : 每次加入一个点,询问1D前缀\max,修改依赖询问。

这东西一个树状数组带走就好,再写CDQ反而麻烦。

总复杂度O(nlog^3n),常数较小。

由于离散化写挂调试一小时,在此警示后人 : 全局变量跳跃使用一定小心。

代码Link + 评测记录

还有很久之前写的3次CDQ嵌套的解法,懒得修了直接丢个评测记录算了。

有一道很类似的题目是P4849 寻找宝藏,只不过还要顺便统计方案数。

[ CDQ嵌套+树状数组 ] : 评测记录

[ 3次CDQ嵌套 ] : 评测记录

首先,这是个静态问题,我们需要按某种顺序将其变成动态问题。

经过认真的思考,容易发现让看得近的数看得远的比较合理(按视野从大到小排序)。

在所有的约束条件中,只有|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 + 评测记录

题解Link

题解Link

题解Link

考虑某种动态问题,静态版本(\texttt{C} 全在 \texttt{Q} 前面)我们会做,而且复杂度只和操作次数相关。

要求可以把 \texttt{C} 分批次向 \texttt{Q} 贡献。

考虑每次在操作中间插一个隔板,只考虑跨越隔板的贡献,此时是静态问题,可以解决。

然后两块之间不再有关系,考虑分治。

一句话来讲 : 以静制动,必须离线

复杂度 : logn*(查询) + 总大小为O(nlogn)的build。

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} 对状态的影响。

至于怎么撤销,可以认为是把对所有数据的改动记录下来然后还原。

题意 : 支持加边删边,询问两点间连通性。

如果没有删边操作,这就是个很简单的并查集。

考虑使用线段树分治,这真就变成了很简单的并查集?

事实上,由于线段树分治会把一个状态传递给两个儿子(类似可持久化的操作树),而并不是经典的一条时间轴,所以均摊分析在线段树分治中会失效。

比如这道题如果写了路径压缩并查集,出题人可以在根节点挂一堆询问,造出一条O(n)的链,然后中间什么都不干。

等到叶节点,突然埋伏你一手,让你把它遍历一次,每个叶子O(n)总的复杂度就是O(n^2),退化了。

这就需要我们使用复杂度严格(或期望)正确的算法,按秩合并并查集正符合这个要求。

至于操作怎么撤回,可以开个栈记录上一次让谁的父亲变为谁,然后倒着做就好了,具体见代码。

代码Link + 评测记录

题意 : 给出一个无向图,每条边都有一个存在时间区间,总时间为[1,k],询问每个时刻该图是不是二分图。

区间就可以看做先加后删,我们先来考虑只有加入的问题。

众所周知,二分图判定的充要条件是 : 没有奇环。

关于路径的奇偶性,我们可以用带权并查集来维护。

每次加入边的时候,如果在联通块内部,查看两个点到根路径长度的奇偶性情况,如果相同,加上新边则形成奇环。

否则,计算出两个根之间的路径奇偶性,赋权并合并。

接下来套用线段树分治即可,注意采用按秩合并。

注意到如果已经形成了奇环,则当前时间区间内就都不可能是二分图了,才做直接跳过即可,可以减小常数。

复杂度O(nlog^2n), 代码Link + 评测记录

这题特殊之处在于,商品(修改)在时间轴上是一个点,而询问是一个区间。

采用逆向思维,把询问分到线段树上去,然后把商品拿来分治。

将每个商品挂到从根到叶子的点上,这样每个点就会有自己区间内的所有商品,拆区间回答询问即可。

在每个节点处,使商品根据商店位置有序,建立可持久化01Trie,就能够查询区间内的xormax.

( 至于怎么查询,可见 P4735 最大异或和 )

这时,由于\max可以分体贡献,我们把挂着的所有询问都拉出来贡献一次即可。

复杂度O(nlog^2n), [代码Link]() + [评测记录]() (准备重写)

对于不同颜色的边可以开多个加权并查集。

这道题的特殊之处在于,无法预知每个修改操作是否执行,也就无法得到每条边的存在区间。

对于一个状态不变的区间,我们分成多段往线段树上挂,显然也不影响正确性。

现在修改操作可以理解为 : 有一个改变颜色的机遇,但是不知道是否会改变。

那么我们把每两个可能的改变操作之间都分段,也无伤大雅。

可以先在同一条边的两个修改之间挂上当前状态,到达询问之后判断是否合法,然后把下一个修改挂上去。

评测记录

首先有一个结论 : 某个图合法当且仅当所有连通块的大小都是偶数。和本文无关就不再赘述。

我们能够发现,两个块合并,一定不会让奇数的块增多,所以我们加边多多益善。

容易想到的方法是kruskal,把边从小到大排序,依次加入,直到合法为止。

现在我们要资瓷动态加边,我们想象一条边什么时候会在决策集合里面 : 加入的时候很优,进入了决策集合,后来随着新边加入被抛弃。

据此容易发现,每条边存在与决策集合中的时间是一个区间。

这让我们看到了线段树分治的希望,可是怎么求出这个区间呢?

考虑从后往前做暴力,显然,每条边第一次加入的时刻就是其区间的末尾。

(坑)

4.整体二分

考虑某种奇怪的问题,询问满足单调性,可以二分。

但是不同的mid需要不同的状态来判定,暴力做代价过高。

这时往往要使用整体二分来一起计算。视情况可以带修。

考虑对应的答案区间[L,R],取其中点mid=\lfloor\frac{L+R}{2}\rfloor

我们把数据结构的状态调整到mid处,然后就可以判定这些询问是大于还是小于mid.

然后把询问分到[L,mid]和(mid,R]中去。

注意到,mid的移动总量是O(nlogn)的,每个询问判定的次数是O(logn)的。

实质上就是最大化询问的共用判定。

题意 : 给定一个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 + 评测记录

题意 : 给定一棵树,有点权,单点修改和询问路径第K小数。

区别在于,这题多了修改。

事实上,我们可以根据时间轴来分析 : 前面的修改能影响后面的询问。

我们在整体二分的时候,把修改也根据权值传下去,同时保证询问和修改的相对顺序不变。

注意要把修改拆分成删除和添加,这两部分可能被分到不同的区间里去。

我们需要树上单点修和路径求和,考虑采用LCT或者树剖。

代码Link + 评测记录

题意 : 给一个序列,多次区间加正数,询问每个位置达到lim[i]所等待的操作数。

对时间轴二分即可。要采用带修整体二分的思想,将已经贡献过的操作减去。

提交记录

题解Link

题解Link

5.猫树分治

考虑某种奇怪的序列静态问题,我们并不会做。

但是,如果所有询问的区间有交集,那么我们就能通过下列算法得出答案。

选取所有询问都包含的某个位置,分别向左向右预处理某些东西。

对于询问的回答,只需要在左端点取信息,在右端点取信息,再组合即可。这要求(答案/状态)能够合并。

然后我们套用猫树分治,就能够处理更一般的情况了。

此外,将分治树存下来,往往就能够做到强制在线。

考虑一堆询问区间和对应的状态区间[L,R]。

我们取状态区间的中点mid=\lfloor\frac{L+R}{2}\rfloor,从mid分别向左右预处理某些信息。

遍历所有询问,如果跨过(mid,mid+1),则合并左右端点信息来回答。

如果在[L,mid]中,则下放到左儿子。

如果在[mid+1,R]中,则下放到右儿子。

继续分治。

(不难发现其实就是序列上的点/边分治,所以上猫树的题目可能可以上点/边分树)

前置芝士 : 线性基,向其中插入的复杂度是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 ))

(坑)

需要SAM技巧,慎入,题解Link

需要线段树技巧,慎入,题解Link

6.二进制分组

还是考虑某个动态问题,静态版本(\texttt{C} 全在 \texttt{Q} 前面)我们会做,而且复杂度只和操作次数相关。

还要满足可以把 \texttt{C} 分批次向 \texttt{Q} 贡献。

有没有发现这个要求和“CDQ分治”一样啊?

奇妙的是,这种方法往往是能够做到在线的。所以这在效果上就是CDQ的强化版。

实现方法多种多样,不特别讲,在下方例题就可以看见了。

加和删本质是同种操作,删可以看成贡献为-1.

先考虑静态的问题怎么做。

对 S 建立AC自动机,在 Fail 树上下传串个数,把匹配到每个节点能获得的匹配次数求出。

然后对于询问,暴力跳自动机求和即可。

现在考虑在线。

我们新加入一个串的时候,不能直接修改现有的AC自动机,又不能重新建造。

如果我们现在有若干个AC自动机瓜分 S ,我们将 T 在每个串上都跑一次即可。

我们可以采用如下的方法来维护这一群AC自动机 :

这道题不使用这种方法实现,因为下一种写法更方便。

代码Link

考虑给定的 (x,y) 与集合中 (a,b) 点积的式子 : ax+by=y(a·\frac{x}{y}+b)

相当于我们在维护若干条 y=ax+b 的直线,每次代入 \frac{x}{y} 当做 x 求所有直线的值的 \max.

现在问题就变成了 :

先考虑静态问题怎么做:

建立线段树,每个节点 [l,r] 上是向量 [L_l,L_r] 形成的凸包。

构造凸包需要排序+单队,使用归并可以省掉排序的log,构造这么一个线段树的复杂度是O(nlogn)。由于不是每条线段都会在凸壳上,实际常数较小。

现在考虑使用二进制分组来解决,此时使用外层线段树的写法公认比较简洁。

外层写一个线段树,加入直线就是单点修。

假如两个儿子都满了,则把自己的凸包build起来。

查询的时候直接在线段树上拆分区间+凸包二分即可(常数较小)。

复杂度O(n\log^2n),这题比较卡常数,建议归并建立凸包。

代码Link

考虑给定的 (x,y) 与集合中 (a,b) 叉积的式子 : bx-ay=x(-a·\frac{y}{x}+b) ，仍然是一次函数问题。

和上一题主要的区别在于，支持在末尾的删除操作。

若某个线段树节点包含有一个被删除的向量，则直接报废。

如果还采用旧的策略，一次删除可能破坏掉一个大块，复杂度退化。

解决办法 ： 在这个区间刚满的时候不 build 这个区间，等到同层的下一个区间也填满的时候再 build 这个区间。

这样，显然每层只有至多 2 个未 build 的区间，查询复杂度仍然可以保证。

删除时，要越过后一个整个区间才能破坏前面已经被 build 的区间，复杂度仍然均摊正确。