Update: 2026.4.30

CDQ 分治是一种分治算法，或者是一种解决问题的思想。其核心思想就是： 将序列递归分成两个子区间，每个问题只处理左区间的修改对右区间的贡献。

CDQ 分治需要对多个维度按照一定规律进行排序，这就要求离线使用，也就是问题本身只能离线才能处理。

CDQ 分治可以解决三类问题：

• 1.与点对有关的问题（数点或者偏序问题）
• 2.优化 1D/1D 动态规划的转移（与偏序有关）
• 3.将带修改 & 查询的动态问题，转化静态问题 (第一维度是时间)

本质上，这些问题都属于“点对之间的贡献问题”。

常见时间复杂度

$T(n)=2T(n/2)+O(n) \longrightarrow O(n\log{n})$

$T(n)=2T(n/2)+O(n\log{n})\longrightarrow O(n\log^2{n})$

分治的两种顺序

1. 递归左区间 [l,mid] $\to$ 递归右区间 [l,mid] $\to$ 双指针解决左区间修改对右区间贡献
2. 递归左区间 [l,mid] $\to$ 双指针解决左区间修改对右区间贡献$\to$ 递归右区间 [l,mid]

有何差别？

1. 第一类问题（点对关系）两种方式都可以。

2. 有时序依赖的问题，第二类(1D/1D 动态规划)和部分第三类问题（单点修改有前后依赖），必须采用第二种分治策略。

---

一、点对有关问题

例1. 【模板】二维偏序

【参考代码】

1. $O(n\log^2{n})$ 写法：点击
2. $O(n\log{n})$ 写法：点击

例2. 【模板】三维偏序

本题加强版(点有重复)P3810三维偏序

【分析】luogu的这道模板题，点有重复，需要处理好点重复这个细节问题。

例3.【模板】四维偏序

【分析】CDQ 套 CDQ

【参考代码】点击

---

二、优化 1D / 1D 动态规划的转移

【注意】由于转移是有顺序，CDQ 必须才有中序遍历方式。

例4. 【模版】一维最长上升子序列

【分析】一维 LIS 问题，可以使用二分、数据结构解决。这里介绍 CDQ 优化

【参考代码】点击

例5.【模板】二维最长上升子序列

【分析】要保持原序列顺序，那么就要满足三维性质：

$id_j<id_i,a_j<a_i,b_j<b_i$

对 $id$ 进行分治，CDQ 考虑第二维，利用数据结构维护第三维度。

注意：要使用中序遍历方式。

【参考代码】点击

例6. P4093[HEOI2016/TJOI2016] 序列

【分析】若 $mn_i$ 表示 $a_i$ 能够变到的最小值，$mx_i$ 表示能变到的最大值，$f_i$ 表示以 $i$ 结尾的最长子序列长度，则转移方程：

$f_j=1+\max_i {f_i}$

其中 $i$ 满足：

• $id_i<id_j$

• $x_i\le mn_j$

• $mx_i \le x_j$

  对 $id$ 分治，解决第一维。 左区间按照 $x$ 排序，右区间按照 $mn$ 排序，然后双指针解决第二维。树状数组维护第三维。

【参考代码】点击

例7. P3364 Cool loves touli

【分析】 $l,s,w,a$ 分别表示等级、力量、智力、攻击力

$f_i$ 表示以 $i$ 结尾最长上升子序列，可以得到转移：

$f_j=1+\max{f_i}$

其中 $i$ 满足

• $l_i < l_j$
• $a_i \le s_j$
• $w_i \le a_j$

对等级 l 分治，cdq 内部左区间对 $a$ 进行排序，右区间对 $s$ 排序，第三维 $w_i \le a_j$ 用树状数组维护。

需要对 $w_i$ 和 $a_j$ 离散化，由于 $s$ 与 $a$ 有大小比较，那么 $a,s,w$ 都需要离散化。

例8. P5621 [DBOI2019] 德丽莎世界第一可爱

【分析】$i$ 转移到 $j$ 需要满足四个属性,类似于 P3769 TATT 可以 KD-tree 或 CDQ 解决

按照其中一维进行分治，剩余三个维度可以 CDQ 套 CDQ 进行。

---

三、动态转静态

所谓动态转静态，本质上就是为所有操作额外加了一个属性 —— 时间戳 $tim$。

$i$ 能对 $j$ 产生贡献，当且仅当：

• $tim_i​ < tim_j$

• $i$ 是修改操作

• $j$ 是查询操作

【注意】如果修改有时序依赖关系，那么必须采用中序遍历。

例8. P4390 [BalkanOI 2007] Mokia 摩基亚

【分析】动态二维数点，K-D tree 和 CDQ 分治都能解决

例9. P4169 [Violet] 天使玩偶/SJY摆棋子

本题有若干操作，动态插入一些点，询问某个点距离最近的点的曼哈顿距离。

暂时忽略掉插入新点操作，查询 $(x,y)$ 最近的点的距离，答案就是： $min\{|x-x_i|+|y-y_i|\}$ , 为了去掉绝对值，我们将询问分成 $4$ 类，分别询问左下、左上、右下、右上方向上距离最近的点的距离，保留最小的就是答案。

• 左下：$min\{(x-x_i)+(y-y_i)\}=(x+y)-max\{x_i+y_i\}$
• 左上：$min\{(x-x_i)+(y_i-y)\}=(x-y)-max\{x_i-y_i\}$
• 右下：$min\{(x_i-x)+(y-y_i)\}=(-x+y)-max\{-x_i+y_i\}$
• 右上：$min\{(x_i-x)+(y_i-y)\}=(-x-y)-max\{-x_i-y_i\}$

我们可以将 $n$ 个点的坐标和 $m$ 个询问的坐标按照横坐标从小到大排序。然后依次扫描。

对于左下方来说：

1. 若扫描到一个点 $(x_i,y_i)$ ,则在树状数组第 $y_i$ 个位置上的值与 $x_i+y_i$ 取最大，同时维护前缀最大。
2. 如果扫描到了一个查询 $(x,y)$ ，则在树状数组，则在树状数组(或线段树)中查询 $[1,y]$ 的最大 $val$ ，该询问就是 $x+y-val$.

上面的做法，排序保证了 $x_i<x$ 的条件，树状数组控制 $y_i<y$ 的条件并维护了 $x_i+y_i$ 的最大值。

对于左上、右上和左下与上述方法类似，例如左上方，还是按照横坐标排序，这时应该是 $x_i≤x,10^6−y_i≤10^6−y$，因此树状数组改成维护 $x_i−y_i$ 的最大值，修改时的位置变为 $10^6−yi+1$，查询时的前缀变为 $[1,10^6-y_i+1]$，剩下两个方向可自行推导。

到这里我们再加上加入操作，除了查询还可能在平面中添加点。有查询和插入操作的动态问题，这就可以用 CDQ 分治分成若干个静态小问题来解决。

那么我们每次递归完左、右区间之后还需要处理左区间修改对右区间查询的影响。可以把第 $l \sim mid$ 项操作中增加的点依次加入一个初始为空的平面，再考虑第 $mid+1∼r$ 项操作中的查询，找到平面上距离最近的点来更新答案，可以用和上面一样的做法。

注意！为了保证每次的时间复杂度之和当前递归的区间内部相关，因此每次不能建立一个新的树状数组，必须在处理完每个区间后再将对树状数组的修改依次还原，保证每次进入和离开时，树状数组都是空的，可以复用。这样整个算法的时间复杂度为 $O((n + m) \log_2^2(n + m))$

注意！ 本题会卡常，需要在 CDQ 分治时进行一些优化，如果区间中只存在添加操作，不存在查询操作，那么不需要处理左区间的修改操作对右区间的查询操作的影响。这是一步效果非常明显的优化(不加这步就只能吸氧了)

【参考代码】点击

学习完毕

{{ select(1) }}

• YES
• NO