CDQ 分治
本页面将介绍 CDQ 分治。
简介
CDQ 分治是一种思想而不是具体的算法,与 动态规划 类似。目前这个思想的拓展十分广泛,依原理与写法的不同,大致分为三类:
- 解决和点对有关的问题。
- 1D 动态规划的优化与转移。
- 通过 CDQ 分治,将一些动态问题转化为静态问题。
CDQ 分治的思想最早由 IOI2008 金牌得主陈丹琦在高中时整理并总结,它也因此得名。1
解决和点对有关的问题
这类问题多数类似于「给定一个长度为 n 的序列,统计有一些特性的点对
CDQ 分治解决这类问题的算法流程如下:
-
找到这个序列的中点
; -
将所有点对
划分为 3 类: 的点对; 的点对; 的点对。
-
将
这个序列拆成两个序列 和 。此时第一类点对和第三类点对都在这两个序列之中; -
递归地处理这两类点对;
-
设法处理第二类点对。
可以看到 CDQ 分治的思想就是不断地把点对通过递归的方式分给左右两个区间。
在实际应用时,我们通常使用一个函数 solve(l,r)
处理 solve(l,mid)
与 solve(mid,r)
来实现的。剩下的第二类点对则需要额外设计算法解决。
例题
给定一个序列,每个点有
三维偏序是 CDQ 分治的经典问题。
题目要求统计序列里点对的个数,那试一下用 CDQ 分治。
首先将序列按
假设我们现在写好了 solve(l,r)
,并且通过递归搞定了 solve(l,mid)
和 solve(mid+1,r)
。现在我们要做的,就是统计满足
稍微思考一下就会发现,那个
为了方便枚举,我们把
当我们插入一个
对于每一个
通过这样一个算法流程,我们就用
对于序列
现在给出
CDQ 分治优化 1D/1D 动态规划的转移
1D/1D 动态规划指的是一类特定的 DP 问题,该类题目的特征是 DP 数组是一维的,转移是
例如,给定一个序列,每个元素有两个属性
这是一个二维最长上升子序列的 DP 方程,即只有
直接转移显然是
我们发现
这个转移过程相对来讲比较套路。假设现在正在处理的区间是
- 如果
,说明 值已经被计算好了。直接令 然后返回即可; - 递归使用
solve(l,mid)
; - 处理所有
, 的转移关系; - 递归使用
solve(mid+1,r)
。
第三步的做法与 CDQ 分治求三维偏序差不多。处理
转移过程的正确性证明
该 CDQ 写法和处理点对间关系的 CDQ 写法最大的不同就是处理
-
用来计算
的所有 值都必须是已经计算完毕的,不能存在“半成品”; -
用来计算
的所有 值都必须能更新到 ,不能存在没有更新到的 值。
上述两个条件可能在
CDQ 分治的递归树如下所示。
执行刚才的算法流程的话,以 solve(1,8)
、solve(5,8)
、solve(7,8)
这 3 个函数中更新完成的,而三次用来更新它的点分别是 solve(1,4)
函数中解决的,更新它的区间是
接着分析我们算法的执行流程:
- 第一个结束的函数是
solve(1,1)
。此时我们发现 的值已经计算完毕了; - 第一个执行转移过程的函数是
solve(1,2)
。此时我们发现 的值已经被转移好了; - 第二个结束的函数是
solve(2,2)
。此时我们发现 的值已经计算完毕了; - 接下来
solve(1,2)
结束, 这段区间的 值均被计算好; - 下一个执行转移流程的函数是
solve(1,4)
。这次转移结束之后我们发现 的值已经被转移好了; - 接下来结束的函数是
solve(3,3)
。我们会发现 的 dp 值被计算好了; - 接下来执行的转移是
solve(2,4)
。此时 在solve(1,4)
中被 转移了一次,这次又被 转移了,因此 的值也被转移好了; solve(4,4)
结束, 的值计算完毕;solve(3,4)
结束, 的值计算完毕;solve(1,4)
结束, 的值计算完毕。- ……
通过模拟函数流程,我们发现一件事:每次 solve(l,r)
结束的时候,solve(l,mid)
已经结束,因此我们每一次执行的转移过程都是合法的,满足第 1 个条件。
在刚才的过程我们发现,如果将 CDQ 分治的递归树看成一颗线段树,那么 CDQ 分治就是这个线段树的 中序遍历函数,因此我们相当于按顺序处理了所有的 DP 值,只是转移顺序被拆开了而已,所以算法是正确的。
例题
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度、并且能够拦截任意速度的导弹,但是以后每一发炮弹都不能高于前一发的高度,其拦截的导弹的飞行速度也不能大于前一发。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。
在不能拦截所有的导弹的情况下,我们当然要选择使国家损失最小、也就是拦截导弹的数量最多的方案。但是拦截导弹数量的最多的方案有可能有多个,如果有多个最优方案,那么我们会随机选取一个作为最终的拦截导弹行动蓝图。
我方间谍已经获取了所有敌军导弹的高度和速度,你的任务是计算出在执行上述决策时,每枚导弹被拦截掉的概率。
将动态问题转化为静态问题
前两种情况使用 CDQ 分治的目的是将序列折半之后递归处理点对间的关系,来获得良好的复杂度。不过在本节中,折半的不是一般的序列,而是时间序列。
它适用于一些「需要支持做 xxx 修改然后做 xxx 询问」的数据结构题。该类题目有两个特点:
- 如果把询问 离线,所有操作会按照时间自然地排成一个序列。
- 每一个修改均与之后的询问操作息息相关。而这样的“修改 - 询问”关系一共会有
对。
我们可以使用 CDQ 分治对于这个操作序列进行分治,处理修改和询问之间的关系。
与处理点对关系的 CDQ 分治类似,假设正在分治的序列是
注意,如果各个修改之间是 独立 的话,我们无需处理 solve(l,mid)
和 solve(mid+1,r)
之间的时序关系(比如普通的加减法问题)。但是如果各个修改之间并不独立(比如说赋值操作),做完这个修改后,序列长什么样可能依赖于之前的序列。此时处理所有跨越 mid 的修改 - 询问关系的步骤就必须放在 solve(l,mid)
和 solve(mid+1,r)
之间。理由和 CDQ 分治优化 1D/1D 动态规划的原因是一样的:按照中序遍历序进行分治才能保证每一个修改都是严格按照时间顺序执行的。
例题
维护一个二维平面,然后支持在一个矩形区域内加一个数字,每次询问一个矩形区域的和。
对于这个问题的静态版本,即“二维平面里有一堆矩形,我们希望询问一个矩形区域的和”,有一个经典做法叫线段树 + 扫描线。具体的做法是先将每个矩形拆成插入和删除两个操作,接着将每个询问拆成两个前缀和相减的形式,最后离线。然而,原题目是动态的,不能直接使用这种做法。
尝试对其使用 CDQ 分治。我们将所有的询问和修改操作全部离线。这些操作形成了一个序列,并且有
我们发现,所有的修改在询问之前就已完成。这时,原问题等价于“平面上有静态的一堆矩形,不停地询问一个矩形区域的和”。
使用一个扫描线在
在这样实现的 CDQ 分治中,同一个询问被处理了
观察上述的算法流程,我们发现一开始我们只能解决静态的矩形加矩形求和问题,但只是简单地使用 CDQ 分治后,我们就可以离线地解决一个动态的矩形加矩形求和问题了。将动态问题转化为静态问题的精髓就在于 CDQ 分治每次仅仅处理跨越某一个点的修改和询问关系,这样的话我们就只需要考虑「所有询问都在修改之后」这个简单的问题了。也正是因为这一点,CDQ 分治被称为「动态问题转化为静态问题的工具」。
维护一个长为
-
将区间
的值修改为 ; -
询问区间
出现了多少种不同的数,也就是说同一个数出现多次只算一个。
一句话题意:区间赋值区间数颜色。
维护一下每个位置左侧第一个同色点的位置,记为
通过将连续的一段颜色看成一个点的方式,可以证明
std::set
来进行处理。这个用 set 维护连续的区间的技巧也被称之为 old driver tree。
PS 国是一个拥有诸多城市的大国。国王 Louis 为城市的交通建设可谓绞尽脑汁。Louis 可以在某些城市之间修建道路,在不同的城市之间修建道路需要不同的花费。
Louis 希望建造最少的道路使得国内所有的城市连通。但是由于某些因素,城市之间修建道路需要的花费会随着时间而改变。Louis 会不断得到某道路的修建代价改变的消息。他希望每得到一条消息后能立即知道使城市连通的最小花费总和。Louis 决定求助于你来完成这个任务。
一句话题意:给定一张图支持动态的修改边权,要求在每次修改边权之后输出这张图的最小生成树的最小代价和。
事实上,有一个线段树分治套 lct 的做法可以解决这个问题,但是这个实现方式的常数过大,可能需要精妙的卡常技巧才可以通过本题,因此不妨考虑 CDQ 分治来解决这个问题。
和一般的 CDQ 分治解决的问题不同,此时使用 CDQ 分治的时候并没有修改和询问的关系来让我们进行分治,因为无法单独考虑“修改一个边对整张图的最小生成树有什么贡献”。传统的 CDQ 分治思路似乎不是很好使。
通过刚才的例题可以发现,一般的 CDQ 分治和线段树有着特殊的联系:我们在 CDQ 分治的过程中其实隐式地建了一棵线段树出来(因为 CDQ 分治的递归树就是一颗线段树)。通常的 CDQ 是考虑线段树左右儿子之间的联系。而对于这道题,我们需要考虑的是父亲和孩子之间的关系;换句话来讲,我们在 $solve(l,r)$
这段区间的时候,如果可以想办法使图的规模变成和区间长度相关的一个变量的话,就可以解决这个问题了。
那么具体来讲如何设计算法呢?
假设我们正在构造
对于一条边来讲:
-
如果最小生成树里所有被修改的边权都被赋成了
,而它未出现在树中,则证明它不可能出现在 这些询问的最小生成树当中。所以我们仅仅在 的边集中加入最小生成树的树边。 -
如果最小生成树里所有被修改的边权都被赋成了
,而它未出现在树中,则证明它一定会出现 这段的区间的最小生成树当中。这样的话我们就可以使用并查集将这些边对应的点缩起来,并且将答案加上这些边的边权。
这样我们就将
那么为什么我们的复杂度是对的呢?
首先,修改过的边一定会加进我们的边集,这些边的数目是
接下来我们需要证明边集当中不会有过多的未被修改的边。我们只会加入所有边权取
现在我们只需证明每递归一层图的点数是
证明点数是
时间复杂度是
代码实现上可能会有一些难度。需要注意的是并查集不能使用路径压缩,否则就不支持回退操作了。执行缩点操作的时候也没有必要真的执行,而是每一层的 kruskal 都在上一层的并查集里直接做就可以了。
参考资料与注释
Footnotes
贡献者:@i207M@邶风@Yuchen@Tifa@kenlig@夜轮_NachtgeistW@mgt@Luckyblock233@Ruitao@StudyingFather@Chrogeek@H-J-Granger@Early@ouuan@LKM@Ir1d@Chro@P6174@shadowice1984@hsfzLZH1@abc1763613206@Xarfa@Xeonacid@Siyuan@ddjxd
本页面最近更新:2/3/2023, 12:00:00 AM,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用