-1.前言

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

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

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

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

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

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

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

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

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

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

---

0.常见的数据结构

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

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

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

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

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

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

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

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

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

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

  一个简单的排除方法是 : 能否支持消除任个操作的影响(删除)。

  • 正确的例子
    • 有序序列(相对BST而言) : 有几个数 ≤Lim≤Lim
    • AC自动机 : 匹配次数
    • 凸壳(动态可以做,只是比较麻烦) : 函数最大值
    • 虚树
    • 后缀数组/SAM(parent tree上构造)
  • 错误的例子
    • 大多数的图上路径问题,因为路径难免会互相影响。

• 可支持假如,撤回,但不支持删除(时间栈)

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

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

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

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

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

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

  也就是说,数据结构本身是能够删除的,但是由于做法的正确性限制无法任意删除。

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

---

1.逆向思维

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

1.1 时间倒流

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

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

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

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

• 例题 : [P1197 JSOI2008]星球大战

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

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

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

1.2 查询/状态的互补

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

• 例题① : P1502 窗口的星星

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

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

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

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

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

我们使用扫描线即可。

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

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

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

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

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

考虑一个修改 uu会对某个询问 vv有贡献的充要条件 : uu在 rtr**t到 vv的路径上。

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

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

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

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

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

---

2.CDQ分治

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

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

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

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

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

• 算法流程

我们考虑如下的操作序列 :

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

1. 我们从正中间分成两半,考虑左边的修改对右边询问的贡献(跨越隔板的贡献),可得:

   \large\underline\texttt{C C Q C}\ \ |\ \ \underline\texttt{C Q Q C}C C Q C ∣ C Q Q C

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

我们采用我们会的静态方法解决这个问题。

然后因为不再需要考虑跨越隔板的贡献,相当于这两块不再有关系,可以分治成子问题。

1. 分治处理左边的 \large\underline\texttt{C C Q C}C C Q C
2. 分治处理右边的 \large\underline\texttt{C Q Q C}C Q Q C

如此分治下去……

---

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

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

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

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

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

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

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

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

• 技巧 : 分治中归并

  有些时候,我们使用 \texttt{C}C 建立静态结构时,直接建立复杂度较劣,但是利用两个儿子余下的信息建立,则更快一些。

  比如说有序序列,直接sort是 O(nlogn)O(nlogn)的,但把两个儿子的有序序列合并是 O(n)O(n)的。

  除此之外还有凸壳(也需要排序)

  此时,我们就要求先分治处理两个子问题(后序遍历),再计算跨越本分隔板的贡献。

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

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

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

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

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

代码Link + 评测记录

---

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

代码Link + 评测记录

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

代码Link + 评测记录

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

  题意 : 要求维护一个数据结构,资瓷两种操作:

  • A 在 SS中加点 (x,y)(x,y)
  • B 给一个观测点 AA,查询目前的 SS内,与 AA最近的哈夫曼距离( dist(A,B)=|A_x-B_x|+|A_y-B_y|dis**t(A,B)=∣A**x−B**x∣+∣A**y−B**y∣)

注意到这个绝对值比较难搞,先考虑 SS中在 AA左下方的点:

有 B_x\leq A_x;B_y\leq A_yB**x≤A**x;B**y≤A**y ,可得 dist(A,B)=(A_x+A_y)-(B_x+B_y)dis**t(A,B)=(A**x+A**y)−(B**x+B**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]=[A**x≤B**x][A**y≤B**y]...[A**z≤B**z](就是 AA每一维都小于等于 BB)

这个题目要求我们做这样的一个DP:

dp[i]=1+\max\limits_{P_j\leq P_i}dp[j]d**p[i]=1+P**j≤P**imaxd**p[j]

我们可以把前面的 dpd**p值看做修改,那么修改依赖会依赖前面的询问。

我们就必须按照 PP递增的顺序来转移,保证转移时前继 DPD**P值已经正确,否则可能漏解。

我们还是先按照一维排序(第一维相同比第二维,再相同比第三维……),同时也按照这样的顺序转移,就能够保证不会漏解。

问题在于,现在我们的CDQ分治需要换个写法。

• 技巧 : DP转移强制中序遍历

  前面的写法是先处理跨越隔板的贡献,再分治下去。

  现在,我们的询问之间也有了依赖关系,必须保证前面的询问回答完,才能准确得到后面询问的贡献。

  我们可以对分治树中序遍历,也就是说在处理完[l,mid]的所有贡献之后再处理跨越隔板的贡献,此时[l,mid]中的询问已经得到了正确结果。

  不过注意,这东西和归并是不兼容的,因为归并要求后序遍历,一个补救的方法是预处理归并存下信息,不过往往会使空间多个 loglog,不推荐。

  另一个补救的方法是,不使用CDQ分治

  一般来说这种依赖关系是会传递的,内层问题也应考虑到这一点。

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

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

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

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

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

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

代码Link + 评测记录

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

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

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

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

• 进阶题③: CF1045G AI robots

  题意 : 给出 nn个三元组 {x_i,r_i,q_i}x**i,r**i,q**i,以及常数 KK

  两个三元组 (i,j)(i,j)之间能贡献当且仅当 (x_i-x_j)\leq\min(r_i,r_j)(x**i−x**j)≤min(r**i,r**j)且 |q_i-q_j|\leq K∣q**i−q**j∣≤K

  问能够贡献的对数。

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

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

在所有的约束条件中,只有 |x_i-x_j|\leq\min(r_i,r_j)∣x**i−x**j∣≤min(r**i,r**j)中含有 \minmin,这和传统的偏序问题大不相同。

如果你按照其他的顺序来数,你就会发现一个尴尬的问题 : 数到的元素不一定看得见接收者。

然而,如果按照视野为序,那么能否贡献就只跟统计者的视野有关了。我们把问题转化成了下面的样子:

动态加入三元组 {x_i,r_i,q_i}x**i,r**i,q**i,并查询目前有的三元组中,满足 |x_i-x_j|\leq r_i∣x**i−x**j∣≤r**i且 |q_i-q_j|\leq K∣q**i−q**j∣≤K的个数。

这就是个裸的动态二维数点了,可使用与上文相同的方法解决。

注意需要容斥拆询问。这题值域很大,但是可以只在 qq的一维离散化。

由于这道题是无序对计数,写起来细节较少。

然而这题 KK相当小,貌似可以直接动态开点线段树艹过去……

代码Link + 评测记录

• 进阶题④ CF848C Goodbye Souvenir

题解Link

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

题解Link

• 进阶题⑥ : BZOJ2961: 共点圆

题解Link

• 浓缩版:

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

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

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

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

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

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

• 技巧① : 分治中归并,考虑利用两个儿子的信息,更快地建立静态结构,需要强制后序遍历。
• 技巧② : 偏序降维 \rightarrow→时间轴,对偏序的某一维排序就变成了动态的低维问题。
• 技巧③ : 有些DP类问题修改会依赖前面的询问,此时则需要按分治树中序遍历计算贡献。

---

3.线段树分治

考虑某种奇怪的动态问题,我们有查询 \texttt{Q}Q ,加入元素 \texttt{A}A ,和删除元素 \texttt{D}D 三种操作。

但是,如果没有 \texttt{D}D 操作,我们就会做。

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

• 算法流程

先考虑一个暴力 : 按照时间点开若干个桶,把每个元素的存在时间段计算出来。

然后,把 \texttt{A}A 操作扔进对应时间段的桶里(如果已经被删掉了,则不加入)。

对于每个桶,做一遍其中的 \texttt{A}A 就能得到这个时间点的正确状态。

容易发现,这个暴力是以每个 \texttt{A}A 多做 O(n)O(n) 次的代价规避了 \texttt{D}D 操作。

考虑使用线段树优化这个暴力,按照时间轴建立线段树,把每个 \texttt{A}A 分配到对应的区间内。

我们让父节点的状态能够向儿子传递,那么只需要在 O(logn)O(log**n)个点里放上 \texttt{A}A ,就能让在这个区间里的所有叶节点都受到这个操作的影响。

然后在线段树上 dfsdfs,到达每个点的时候先完成这个点所有的 \texttt{A}A ,然后:

向左儿子递归处理,此时左儿子自然继承了父亲的状态。

向右儿子递归处理,此时左儿子自然继承了父亲的状态。

向老爸借了东西,还的时候要纤毫不损,撤销这个点所有的 \texttt{A}A 对状态的影响。

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

• 例题① Loj#121. 「离线可过」动态图连通性

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

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

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

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

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

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

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

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

代码Link + 评测记录

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

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

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

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

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

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

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

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

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

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

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

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

  有若干个顾客,各有一个参数 xx

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

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

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

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

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

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

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

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

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

• 进阶题① : CF576E Painting Edges

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

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

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

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

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

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

评测记录

• 进阶题② : CF603E Pastoral Oddities

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

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

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

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

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

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

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

• 技巧 : 当操作的状态或者时间区间不确定的时候,可以按某种顺序分治以恰好得到信息

  比如上一题,就必须按照从左到右的顺序分治,以从前面的询问得到后面的颜色信息。

  更毒瘤的是,本题连时间区间都未知。不过这个区间的左端点我们是知道的。

  考虑反过来分治(时间倒流),先递归右儿子,在叶节点处,我们得到目前半成品图的最大边权 ww

  把所有剩余的边权大于 ww的边尝试加入,对于那些加进去的边,就能得到其存在区间的末尾。

  一旦已满足条件就不加了,由于多多益善,中间是不会无故丢掉某条边的,所以每条边只会被考虑一次。

(坑)

---

4.整体二分

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

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

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

• 算法流程

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

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

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

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

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

---

• 例题① : [P1527 国家集训队]矩阵乘法

题意 : 给定一个 N\times NN×N的矩阵,多次询问一个子矩形的第 KK小数。

N\leq 600;q\leq 60000N≤600;q≤60000 ,时限 \texttt{1.5s}1.5s

先将矩阵内的数字离散化并排序。

分治到 [L,R][L,R]时,将不超过 midmid的数字全部加入二维树状数组(单点+1)

根据上一次的状态加或者删数字。 midmid的总变化量是 O(n^2logn)O(n2log**n)的,这部分的复杂度就是 O(n^2log3n)O(n2log3n)

然后判定就是矩阵查询,和 KK比较。这部分复杂度是 O(qlog^3n)O(qlo**g3n)

由于每个数对单个询问的贡献方式固定,还有另一种写法 :

考虑类似线段树二分,我们进入右子树时会抛弃左子树的信息。

我们把矩阵中的数字带着一起分治,分治到 [L,R][L,R]时,我们只加入 [L,mid][L,mid]的数字,然后判定。

如果 KK大于查询值 cc,则减去 cc,分配到右区间,这样就和大小在左区间的数无关了。

注意判定完毕之后要清空树状数组。

复杂度依然是 O((n^2+q)log3n)O((n2+q)log3n),常数较小。

一开始挂了几发,对着代码看了半小时啥也没看出来很自闭,后来拍了才发现是数组开小了……

代码Link + 评测记录

---

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

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

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

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

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

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

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

• 技巧 : 带修整体二分

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

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

代码Link + 评测记录

---

• 进阶题① [P3527 POI2011]MET-Meteors

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

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

提交记录

• 进阶题② CFgym102354B. Yet Another Convolution

题解Link

• 进阶题③ P5163 WD与地图

题解Link

5.猫树分治

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

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

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

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

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

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

• 算法流程

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

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

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

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

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

继续分治。

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

---

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

前置芝士 : 线性基,向其中插入的复杂度是 O(\log c)O(logc)的,合并两个线性基是 O(\log^2c)O(log2c)的.

有一个显然的暴力 : 建立线段树,暴力合并 O(\log n)O(logn)个线性基,复杂度 O(n\log n\log c+q\log n\log^2c)O(nlognlogc+qlognlog2c),

考虑如果所有区间都包含 midmid,我们从 midmid向左向右扩展,每个询问只需要合并左右端点的两个线性基即可。

套用猫树分治,额外的代价仅为 O(q\log n)O(qlogn),总复杂度为 O(n\log n\log c+q(\log n+\log^2c ))O(nlognlogc+q(logn+log2c))

(坑)

• 进阶题① : [P5576 CmdOI2019]口头禅

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

• 进阶题② : [P6109 Ynoi2009]rprmq

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

---

6.二进制分组

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

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

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

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

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

• 例题① : CF710F String Set Queries

  题意 :

  • 支持向集合 SS中加,删字符串。
  • 给出文本串 TT,询问 SS中所有串出现的总次数。

  强制在线。

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

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

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

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

现在考虑在线。

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

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

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

• 写法① : jiry : 2048

  加入新串时,查看上一个AC自动机中的串数是否与自己相等,如果相等则合并,不断重复这个过程。

  实际上写代码的时候,可以一口气找到合并的结束位置,然后一口气合并,可以减小常数。

  目前存留的AC机个数,就相当于串数的二进制表示中 11 的个数,为 O(logn)O(log**n)

  如果一个串待在大小 2^i2i的AC机里,就说明他被合并了 ii 次,而 nn 个串最多合出 2^{logn}2log**n ,每个串被合并的次数也就是 O(logn)O(log**n)。

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

• 写法② : 替罪均摊

  加入新串时,查看上一个AC自动机中的串总长是否小于自己的 \alphaα倍。

  如果是,则将两堆合并。

  由于每一个AC机总串长都会比上一个至少减小 \alphaα倍,所以总个数就是 O(log_{\alpha}L)O(logαL)的。

  重构的复杂度考虑均摊证明,分层考虑势能。

  加入新串时,在当前层增加了 lenlen的势能(串长)。

  合并时,设本层势能为 hh,则消耗的时间为 \Theta((1+\alpha)h)Θ((1+α)h)。合并后,本层势能转移到上一层。

  考虑到势能最多会上升 O(log_{\alpha}L)O(logαL)层,而势能与时间之间的兑换是 1:(1+\alpha)1:(1+α) 的,所以重构总复杂度为 O((1+\alpha)Llog_{\alpha}L)O((1+α)Llogα**L)

  实际上可以微调 \alphaα来实现常数平衡,常取 \alpha=2α=2。

代码Link

• 例题② : [P3309 SDOI2014]向量集

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

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

现在问题就变成了 :

• push_back一条直线。
• 查询某个区间的直线在 x=cx=c 时的最大取值。

先考虑静态问题怎么做:

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

构造凸包需要排序+单队,使用归并可以省掉排序的 loglog,构造这么一个线段树的复杂度是 O(nlogn)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*$ 这个区间。

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

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