CDQ 分治 学习笔记

CDQ 分治的思想最早由 IOI2008 金牌得主陈丹琦在高中时整理并总结，它也因此得名。

简介

CDQ 分治是一种思想而不是具体的算法，与 动态规划 类似。目前这个思想的拓展十分广泛，依原理与写法的不同，大致分为三类：

• 解决和点对有关的问题。
• 一维动态规划的优化与转移。
• 通过 CDQ 分治，将一些动态问题转化为静态问题。

解决和点对有关的问题

这类问题多数类似于「给定一个长度为 n 的序列，统计有一些特性的点对 $(i,j)$ 的数量 / 找到一对点 $(i,j)$ 使得一些函数的值最大」。

CDQ 分治解决这类问题的算法流程如下：

1. 找到这个序列的中点 $mid$；

2. 将所有点对 $(i,j)$ 划分为 3 类：

   1. $1\le i\le mid,1\le j\le mid$ 的点对；
   2. $1\le i\le mid,mid+1\le j\le n$ 的点对；
   3. $mid+1\le i\le n,mid+1\le j\le n$ 的点对。

3. 将 $(1,n)$ 这个序列拆成两个序列 $(1,mid)$ 和 $(mid+1,n)$。此时第一类点对和第三类点对都在这两个序列之中；

4. 递归地处理这两类点对；

5. 设法处理第二类点对。

可以看到 CDQ 分治的思想就是不断地把点对通过递归的方式分给左右两个区间。

在实际应用时，我们通常使用一个函数 solve(l,r) 处理 $l\le i\le r,l\le j\le r$ 的点对。上述算法流程中的递归部分便是通过 solve(l,mid) 与 solve(mid,r) 来实现的。剩下的第二类点对则需要额外设计算法解决。

例题：三维偏序

题意：给定一个序列，每个点有 $a_i,b_i,c_i$ 三个属性，试求：这个序列里有多少对点对 $(i,j)$ 满足 $a_j\le a_i$ 且 $b_j\le b_i$ 且 $c_j\le c_i$ 且 $j\ne i$。

解题思路

三维偏序是 CDQ 分治的经典问题。

题目要求统计序列里点对的个数，那试一下用 CDQ 分治。

• 首先将序列按 $a$ 排序。
• 假设我们现在写好了 solve(l,r)，并且通过递归搞定了 solve(l,mid) 和 solve(mid+1,r)。现在我们要做的，就是统计满足 $l\le i\le mid$,$mid+1\le j\le r$ 的点对 $(i,j)$ 中，有多个点对还满足 $a_i<a_j$,$b_i<b_j$,$c_i<c_j$ 的限制条件。
• 稍微思考一下就会发现，那个 $a_i<a_j$ 的限制条件没啥用了：已经将序列按 $a$ 排序，则 $a_i<a_j$ 可转化为 $i<j$。既然 $i$ 比 $mid$ 小，$j$ 比 $mid$ 大，那 $i$ 肯定比 $j$ 要小。现在还剩下两个限制条件：$b_i<b_j$ 与 $c_i<c_j$, 根据这个限制条件我们就可以枚举 $j$, 求出有多少个满足条件的 $i$。
• 为了方便枚举，我们把 $(l,mid)$ 和 $(mid+1,r)$ 中的点全部按照 $b$ 的值从小到大排个序。之后我们依次枚举每一个 $j$, 把所有 $b_i<b_j$ 的点 $i$ 全部插入到某种数据结构里（这里我们选择 树状数组）。此时只要查询树状数组里有多少个点的 $c$ 值是小于 $c_j$ 的，我们就求出了对于这个点 $j$，有多少个 $i$ 可以合法匹配它了。
• 当我们插入一个 $c$ 值等于 $x$ 的点时，我们就令树状数组的 $x$ 这个位置单点 + 1，而查询树状数组里有多少个点小于 $x$ 的操作实际上就是在求 前缀和，只要我们事先对于所有的 $c$ 值做了 离散化，我们的复杂度就是对的。
• 对于每一个 $j$，我们都需要将所有 $b_i<b_j$ 的点 $i$ 插入树状数组中。由于所有的 $i$ 和 $j$ 都已事先按照 $b$ 值排好序，这样的话只要以双指针的方式在树状数组里插入点，则对树状数组的插入操作就能从 $O(n^2)$ 次降到 $O(n)$ 次。
• 通过这样一个算法流程，我们就用 $O(n\log n)$ 的时间处理完了关于第二类点对的信息了。此时算法的时间复杂度是 $T(n)=T(\lfloor \frac{n}{2}\rfloor )+T(\lceil \frac{n}{2}\rceil )+O(n\log n)=O(n{\log }^{2}n)$。