1. 简介
CDQ分治是一种思想，类似于动态规划，依照原理和写法的不同，大致分为3类：
-
解决与点对相关的问题
-
1D动态规划的优化及转移
-
通过CDQ分治，将一些动态问题转化为静态问题
2. 解决与点对相关的问题
2.1. 流程
1.找到序列的中点mid
2.将所有的点对(i,j)划分为三类
a. \(i\le mid,j\le mid\)
b. \(i\le mid,j>mid\)
c. \(i>mid,j>mid\)
3.将原序列拆成(1,mid),(mid+1,n)两个序列，第一和第三类可以递归处理，第二类则另外想办法
2.2. 例题
oj:https://gxyzoj.com/d/gxyznoi/p/P18
题目描述
有 $ n $ 个元素，第 $ i $ 个元素有 $ a_i,b_i,c_i $ 三个属性，设 $ f(i) $ 表示满足 $ a_j \leq a_i $ 且 $ b_j \leq b_i $ 且 $ c_j \leq c_i $ 且 $ j \ne i $ 的 \(j\) 的数量。
对于 $ d \in [0, n) $，求 $ f(i) = d $ 的数量。
输入格式
第一行两个整数 $ n,k $，表示元素数量和最大属性值。
接下来 $ n $ 行，每行三个整数 $ a_i ,b_i,c_i $，分别表示三个属性值。
输出格式
$ n $ 行，第 $ d + 1 $ 行表示 $ f(i) = d $ 的 $ i $ 的数量。
提示
$ 1 \leq n \leq 10^5$，$1 \leq a_i, b_i, c_i \le k \leq 2 \times 10^5 $。
2.3. 解法
这是一道和点对有关的问题
首先将三元组按a排序
假设此时已经写好了solve(l,r)，且通过求解得到了solve(l,mid),solve(mid+1,r)，此时，可以考虑如何求解第二部分的答案
可以发现，此时因为已经排序，所以\(a_i\le a_j\)的条件已经没什么用了，那么此时只剩下两个条件，
标签：le,分治,mid,笔记,leq,solve,CDQ From： https://www.cnblogs.com/wangsiqi2010916/p/18155809