CDQ分治
闲话
依旧是一年前写的。
一些定义
分治中心：就是常说的 midmidmid，划分两个区间的分割点，普通分治取 mid=⌊l+r2⌋mid = \lfloor \frac{l+r}{2} \rfloormid=⌊2l+r ⌋。
引入
分治这个东西的本质就是做信息划分，通过把信息划分成两个部分然后对一个部分的信息做整体合并，另一个信息做整体查询，做到优化时间复杂度的目的。
比如说这样一个经典的问题：求一个序列的逆序对数。形式化来说就是求出 i<ji<ji<j 且 ai>aja_i > a_jai >aj 的二元组 (i,j)(i,j)(i,j) 个数，这里可以使用数据结构来做，但是先抛开它不谈。
你可能听说过：这不是归并排序的时候顺便求一下就可以了吗？当然是对的，但是它的本质是什么。
归并排序的分治过程是这样的：
* 先递归处理区间 [l,mid][l,mid][l,mid] 和 [mid+1,r][mid+1,r][mid+1,r]，将这两个区间里的数排序。
* 依次比较两个区间的每个数，分别维护一个头指针，记作 l1,l2l_1,l_2l1 ,l2 ，比较这两个数的大小，将较小的一个放到临时数组里做归并。
* 将临时数组的信息复制到原数组。
计算逆序是在第二步，我们考虑 [mid+1,r][mid+1,r][mid+1,r] 天然的性质：这里面的所有数的原编号都大于 [l,mid][l,mid][l,mid]，这是毋庸置疑的。同时，考虑计算贡献，由于两个数组此时是单调的，所以此时 [l,mid][l,mid][l,mid] 中比 l2l_2l2 位置上大的数区间为 [l1,mid][l_1,mid][l1 ,mid]，贡献就是 mid−l1+1mid-l_1+1mid−l1 +1，当然需要满足 al1>al2a_{l_1} > a_{l_2}al1 >al2 。
时间复杂度是 O(nlogn)O(n \log n)O(nlogn) 的，递归 logn\log nlogn 层并且一层均摊 O(n)O(n)O(n)。
一般偏序问题
比较形式化的问题。
偏序问题的定义
简单来说就是有 nnn 个元素，每个元素有若干组信息（维度），然后偏序就是两个元素的每个维度上的信息满足一些大小关系。
比如说刚刚的逆序对问题可以把每个数看做二元组 (ai,i)(a_i,i)(ai ,i)，满足贡献就是 $a_i > a_j $ 并且 i<ji < ji<j，这就是一个偏序问题。
CDQ基本思路
刚刚解决逆序对问题我们是按照这个思路走的：
* 将区间内的点对按照位置划分成三部分:
1. l≤i≤midl\le i\le midl≤i≤mid 且 mid+1≤j≤rmid+1 \le j \le rmid+1≤j≤r，左部点在 [l,mid][l,mid][l,mid] 右部点在 [mid+1,r][mid+1,r][mid+1,r]。
2. l≤i<j≤midl\le i < j\le midl≤i<j≤mid，都在 [l,mid][l,mid][l,mid]。
3. mid+1≤i<j≤rmid+1\le i < j\le rmid+1≤i<j≤r，都在 [mid+1,r][mid+1,r][mid+1,r]。
* 分治处理第一类区间，递归去做另外的子问题。
这是分治的基本思路，当然可能递归顺序有所不同，但是本质上都是处理第一部分的点对。
同时，对于偏序问题而言我们有一个设计思路：排序维护单调性。
以三维偏序为例，每个元素有 (xi,yi,zi)(x_i,y_i,z_i)(xi ,yi ,zi ) 三维，一个点对合法的条件是：同时满足 xi≤xj,yi≤yj,zi≤zjx_i \le x_j,y_i \le y_j,z_i \le z_jxi ≤xj ,yi ≤yj ,zi ≤zj 。
这个思路很重要，设计算法就是这样设计，敲黑板！
和刚刚的归并排序一样，我们强制让一维有序，这一点我们对原数组排个序。分治的时候就时刻保证 [mid+1,r][mid+1,r][mid+1,r] 中的所有数至少在一维上相对 [l,mid][l,mid][l,mid] 的数是有序的，这里我们按 xxx 从小到大排序。
既然如此，我们也就不在意它们的顺序，不妨让 [l,mid][l,mid][l,mid] 和 [mid+1,r][mid+1,r][mid+1,r] 在第二维 yyy 上分别有序，这样维护出来单调性就可以通过双指针来动态维护 [mid+1,r][mid+1,r][mid+1,r] 某一个位置 ididid 的偏序信息，本质是一个集合。
第三维此时，排序有点排不动了......但是我们可以把这个统计问题看做是算一个前缀信息，换句话说：序列上单点加区间求和。树状数组或者线段树随便上一个就可以了。
回顾一下 CDQ 分治的设计思路：
* 整体排序，保证第一维单调性。
* 做归并，合并信息前保证 [l,mid][l,mid][l,mid] 和 [mid+1,r][mid+1,r][mid+1,r] 在第二维相对有序。
* 通过数据结构维护第三维信息。
恭喜你学会了 CDQ 分治，这是模版题。
变种
一些题的套路，考来考去其实都是这样的。
时间轴上的问题
一些维护操作的问题一般都会有操作时效性，就是说一个操作只对它后面的询问或者操作有影响，这是天然的一维排序。
考虑这个问题：在一个二维平面直角坐标系上支持单点加一个数，统计某个矩形内所有数的和。
首先矩形我们有一个常规的做法：二维差分。对于一组询问 (x1,y1,x2,y2)(x_1,y_1,x_2,y_2)(x1 ,y1 ,x2 ,y2 ) 我们拆分成四个询问 (x1−1,y1−1)，(x2,y1−1),(x1−1,y2),(x2,y2)(x_1-1,y_1-1)，(x_2,y_1-1),(x_1-1,y_2),(x_2,y_2)(x1 −1,y1 −1)，(x2 ,y1 −1),(x1 −1,y2 ),(x2 ,y2 )。也就是矩形差分，画图的话大概是这样的：
所以我们只需要考虑统计三元组 (xi,yi,ti)(x_i,y_i,t_i)(xi ,yi ,ti )，也就是满足 xi≤xj,yi≤yj,ti≤tjx_i \le x_j,y_i \le y_j,t_i \le t_jxi ≤xj ,yi ≤yj ,ti ≤tj 的信息。
时间是天然有序的，直接分治就可以只需要考虑坐标维，使用 BIT（树状数组）就可以了。
代码非常好写。
优化转移
这个实际上基本才是 CDQ 的基本用途，用于优化一些条件类似偏序的动态规划转移。
来看这样一个问题:P4093 [HEOI2016/TJOI2016] 序列
序列变化只是干扰因素。我们考虑动态规划，记一个位置的可能最大值为 mximx_imxi ，可能最小值为 mnimn_imni ，fif_ifi 表示以 iii 结尾的答案。满足以下条件时可进行转移：
j<ij < ij<i，mxj≤aimx_j \leq a_imxj ≤ai ，aj≥mnia_j \geq mn_iaj ≥mni ，此时 fj+1f_j + 1fj +1 可转移到 fif_ifi 。由于序列每次最多产生一种变化，所以只需考虑两种极端情况。
此时，考虑 CDQ 分治的时候，我们的递归顺序不太一样，是先递归 [l,mid][l,mid][l,mid] 然后根据 [l,mid][l,mid][l,mid] 的信息对 [mid+1,r][mid+1,r][mid+1,r] 做批量更新，然后考虑继续递归 [mid+1,r][mid+1,r][mid+1,r]。
原理很简单，分析下转移路径的顺序就可以了。本质上，就是在分治树上做中序遍历，分治的顺序同时也很重要。
课后例题
P2487 [SDOI2011] 拦截导弹
P3157 [CQOI2011] 动态逆序对
P4169 [Violet] 天使玩偶/SJY摆棋子
P8575 「DTOI-2」星之河
P10633 BZOJ2989 数列/BZOJ4170 极光
