-1.前言

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

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

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

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

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

要求 : 什么样的数据结构可以使用这个技巧呢?
效果 : 使用这个技巧我们能玩什么exciting的操作呢?
扩展 : 这个技巧在其他奇奇怪怪的地方有什么用处呢?这个技巧有什么本质理解吗?

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

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

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

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

0.常见的数据结构

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

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

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

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

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

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

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

方便构造,但不方便修改(静态)

贡献可以“分体”计算,把信息(修改)分成几份,分别构造数据结构,分别查询,可以合并答案。

也就是说,不能考虑操作之间的互相影响。

一个简单的排除方法是 : 能否支持消除任个操作的影响(删除)。
- 正确的例子
  - 有序序列(相对BST而言) : 有几个数 $≤Lim$
  - AC自动机 : 匹配次数
  - 凸壳(动态可以做,只是比较麻烦) : 函数最大值
  - 虚树
  - 后缀数组/SAM(parent tree上构造)
- 错误的例子
  - 大多数的图上路径问题,因为路径难免会互相影响。
可支持假如,撤回,但不支持删除(时间栈)

理论上,所有非均摊的数据结构都可以撤回。

一个显然的方法是 : 开栈记录所有的数组修改,然后反着做回去。

对于需要均摊分析复杂度的数据结构,也并非一定无法撤回,如果能够把撤回操作描述成这个数据结构的原操作的话,仍然能使用均摊分析。

举个例子 : LCT维护最小生成树。

由于每次操作时加入一条边会删去环上最大边,丢失了原图的信息,肯定是不能支持任意删除的。

但是撤回的时候,只需要把连断边操作反着做就好了。

也就是说,数据结构本身是能够删除的,但是由于做法的正确性限制无法任意删除。
- 正确的例子
  - 并查集(按秩合并)
  - LCT维护最小生成树
  - 线性基
  - 动态凸壳(虽然一次可能删掉很多点,把删去的点放到别处暂存即可)
- 错误的例子
  - 大多数均摊数据结构,如果不支持删除,那就不用考虑了。
  - 静态的就更不用说了。

1.逆向思维

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

1.1 时间倒流

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

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

常见的有删除

\Leftrightarrow

插入 ;分裂

\Leftrightarrow

合并等等。

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

例题 : P1197 [JSOI2008]星球大战

题意 : 删边求联通块个数。

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

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

1.2 查询/状态的互补

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

例题① : P1502 窗口的星星

题意 : 给一个固定的平行于坐标轴的 $r*c$ 矩形,问其最多能在平面直角坐标系中框柱几个点。

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

设矩形左上角为

A

,一个点能被统计到的充要条件 : 点在矩形内。

然而,我们如果把每个点变成以其为右下角的

r*c

矩形,其能贡献的充要条件变为 :

A

在产生的矩形内。

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

我们使用扫描线即可。

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

例题② : P2982 [USACO10FEB]慢下来Slowing down

题意 : 给出一棵树,要求支持单点加,从根到某个点的路径求和。

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

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

考虑一个修改

u

会对某个询问

v

有贡献的充要条件 :

u

在

rt

到

v

的路径上。

也就等价于 :

u

是

v

的父亲,

v

在

u

的子树内。

现在就变成了 : 给出

v

统计其在多少个点的子树内。

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

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

其实这东西在DP里面也有应用,先咕着

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)

。

例题① : P3374 【模板】树状数组 1 (~~纯属娱乐~~)

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

初始全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 + 评测记录

例题② : P3810 【模板】三维偏序（陌上花开）

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

技巧 : 偏序降维 $\rightarrow$ 时间轴

偏序问题是一类比较常见的问题,一般来讲,对某一维排序作为时间轴,可以降维并转化成动态问题。

也就是说,按照第一维从小到大加入元素,那么后面的点会被前面的点贡献,就满足了偏序要求。

现在就转化成了 : 支持加点,查询前缀2D矩阵点值和。

不过注意,只有静态问题能这么做,因为你只有一个时间轴。

还有一个问题是,若果有两个点的位置相同,而且比较是 $[\leq]$ 的话,这两个点会互相贡献。

有些时候可以把重( $ch\acute ong$ )点缩成一个,有些时候可以提前补算从后向前的贡献,本题采用后者。

如果补算贡献的话,分治中的排序一定要采用稳定排序,可以用stable_sort。

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

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

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

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

\rightarrow

时间轴”

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

直接树状数组就好了,复杂度

O(mlogm)

,注意这里不能无脑memset初始化,要把上次的操作撤销来达到清空的目的。

总复杂度就是

O(nlog^2n)

,代码实现较之其他方法较为简易,常数也不大。

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

代码Link + 评测记录

当然,这是使用树状数组解决二维静态数点问题,而前面讲了,CDQ分治也能做,而且复杂度为

O(mlogm)

(需要归并技巧),一样的复杂度。

代码Link + 评测记录

进阶题① : P4169 [Violet]天使玩偶/SJY摆棋子

题意 : 要求维护一个数据结构,资瓷两种操作:
- 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 + 评测记录

进阶题② : P3769 [CH弱省胡策R2]TATT

首先把重点合并。

定义高维点的比较 :

[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 + 评测记录

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

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

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

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

进阶题③: CF1045G AI robots

题意 : 给出 $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 + 评测记录

进阶题④ CF848C Goodbye Souvenir

题解Link

进阶题⑤ : P4027 [NOI2007]货币兑换

题解Link

进阶题⑥ : BZOJ2961: 共点圆

题解Link

浓缩版:

考虑某种动态问题,静态版本(

\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. 「离线可过」动态图连通性

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

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

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

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

比如这道题如果写了路径压缩并查集,出题人可以在根节点挂一堆询问,造出一条

O(n)

的链,然后中间什么都不干。

等到叶节点,突然埋伏你一手,让你把它遍历一次,每个叶子

O(n)

总的复杂度就是

O(n^2)

,退化了。

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

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

代码Link + 评测记录

例题② : P5787 二分图 /【模板】线段树分治

题意 : 给出一个无向图,每条边都有一个存在时间区间,总时间为

[1,k]

,询问每个时刻该图是不是二分图。

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

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

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

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

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

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

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

复杂度

O(nlog^2n)

, 代码Link + 评测记录

例题③ : P4585 [FJOI2015]火星商店问题

题意 : 有一排 $n$ 个商店,某个商店会在某个时刻购入权值为 $v$ 的商品。

有若干个顾客,各有一个参数 $x$

询问在 $[l,r]$ 商店内购买进货时间在 $[tl,tr]$ 的商品中, $v\ {\bf xor}\ x$ 的最大值。

顾客和进货操作的总量不超过 $m$ ,有 $n,m\leq 10^5$ ,时限 $\texttt{2s}$ .

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

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

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

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

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

这时,由于

\max

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

复杂度

O(nlog^2n)

, 代码Link + 评测记录 (准备重写)

进阶题① : CF576E Painting Edges

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

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

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

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

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

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

评测记录

进阶题② : CF603E Pastoral Oddities

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

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

容易想到的方法是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 [国家集训队]矩阵乘法

题意 : 给定一个

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 + 评测记录

例题② :P4175 [CTSC2008]网络管理

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

K

小数。

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

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

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

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

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

技巧 : 带修整体二分

如果修改可以向询问分体贡献(类比CDQ),贡献容易合并,我们就可以把修改带着一并二分。

注意,题目中原有的修改可能会在二分的意义下有变化。比如赋值 $\rightarrow$ 删除&加入。

代码Link + 评测记录

进阶题① P3527 [POI2011]MET-Meteors

题意 : 给一个序列,多次区间加正数,询问每个位置达到

lim[i]

所等待的操作数。

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

提交记录

进阶题② CFgym102354B. Yet Another Convolution

题解Link

进阶题③ P5163 WD与地图

题解Link

5.猫树分治

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

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

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

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

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

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

算法流程

考虑一堆询问区间和对应的状态区间

[L,R]

。

我们取状态区间的中点

mid=\lfloor\frac{L+R}{2}\rfloor

,从

mid

分别向左右预处理某些信息。

遍历所有询问,如果跨过

(mid,mid+1)

,则合并左右端点信息来回答。

如果在

[L,mid]

中,则下放到左儿子。

如果在

[mid+1,R]

中,则下放到右儿子。

继续分治。

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

例题① : P6240 好吃的题目
例题② : CF1100F Ivan and Burgers

前置芝士 : 线性基,向其中插入的复杂度是

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]口头禅

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

进阶题② : P6109 [Ynoi2009]rprmq

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

6.二进制分组

还是考虑某个动态问题,静态版本(

\texttt{C}

全在

\texttt{Q}

前面)我们会做,而且复杂度只和操作次数相关。

还要满足可以把

\texttt{C}

分批次向

\texttt{Q}

贡献。

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

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

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

例题① : CF710F String Set Queries

题意 :
- 支持向集合 $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

例题② : P3309 [SDOI2014]向量集

考虑给定的

(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

例题③ : Uoj#191. 【集训队互测2016】Unknownb

考虑给定的

(x,y)

与集合中

(a,b)

叉积的式子 :

bx-ay=x(-a·\frac{y}{x}+b)

，仍然是一次函数问题。

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

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

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

解决办法：在这个区间刚满的时候不

build

这个区间，等到同层的下一个区间也填满的时候再

build

这个区间。

这样，显然每层只有至多

2

个未

build

的区间，查询复杂度仍然可以保证。

删除时，要越过后一个整个区间才能破坏前面已经被

build

的区间，复杂度仍然均摊正确。

一些常用的数据结构维护手法（摘自kuvsl99s）

文章操作

-1.前言

0.常见的数据结构

1.逆向思维

1.1 时间倒流

1.2 查询/状态的互补

2.CDQ分治

3.线段树分治

4.整体二分

5.猫树分治

6.二进制分组

相关推荐

评论

一些常用的数据结构维护手法（摘自kuvsl99s）