A.\(CDQ\) 分治
特别基础的教程略。
\(CDQ\)分治的优缺点：
( 1 )优点：代码量少，常数极小，可以降低处理维数。 ( 2 )缺点：必须离线处理。
\(CDQ\)分治与其他分治最本质的不同在于：
分治到达\([L,R]\)时，分治处理\([L,mid]\)与\([mid+1,R]\)
然后递归上来合并的时候：只考虑 [L,mid]中元素 对 [mid+1,R] 中元素的影响
看起来这句话非常简单，但只要正真理解了这句话，也就理解了\(CDQ\)分治。
只要是满足这个原则的分治，都是可以称作\(CDQ\)分治的。 下面给出几个例子，都是为了理解这句话：例题1:
给定长度为\(10^5\)的一个序列，有一下两种操作：
（1）type=1：x val ,把序列第x位置的元素加上val （2）type=2：x y , 求解[x,y]元素值的和
树状数组大水题.....
如果用\(CDQ\)分治呢？(例题2：
三维偏序问题：
给定\(n\)个元素，每个元素有三个属性\(a,b,c\)。 定义\(f(i) = \sum_{i=1}^n [i!=j]\times [a_j<a_i 且 b_j<b_i 且 c_j<c_i]\) 试计算\(f(1),f(2),...f(n)\)，数据范围 \(n \leq 10^5\)。
三维偏序是\(CDQ\)分治的最经典应用。
先确定分治原则： 建立三元组\((a,b,c)\)，外部先按照\(a\)排序，消除\(a\)的影响。 然后分治内部以\(b\)为准则进行归并。此时我们保证了\(a_j<a_i\)与\(b_j<b_i\) 第三维\(c_j<c_i\)怎么办？用以\(c\)值建立权值树状数组维护即可。 具体流程为：（1）递归处理\([L,mid]\)与[mid+1,R]；
（2）以\(b\)为准则归并，其中： （ 2>1 ）若为\([L,mid]\)元素，将其\(c\)值插入权值树状数组 （ 2>2 ）若为\([mid+1,R]\)元素，在权值线段树中查询小于其\(c\)值的元素个数。 （3）回溯;
观察到处理时，依旧满足上面\(CDQ\)分治的特性。
如果偏序原则中为\(\leq\)即可，那么需要先去重。具体代码见\(CDQ\)分治的写法
一个非常大的误区：\(CDQ\)分治一定要归并或边归并边处理。
这其实是不对的，上面说过，只要满足\(CDQ\)分治原则就可以称为\(CDQ\)分治。 所以\(CDQ\)分治的写法其实是多重多样，甚至不拘一格的。B.CDQ分治中分治原则的确定
\(CDQ\)分治中的一个难点就是确定分治原则。
在我们分治前，我们会确定元素的分治多元组。 分治多元组的确定关键是看分治中对答案的影响因素。 下面给两个非常经典的例题：例题3：
序列初始为空，接下来每次会在指定位置\(i\)插入一个元素\(x\)
求每次插入后，序列中的逆序对个数。 保证插入元素的值不重复，数据范围\(n \leq 10^5\)
确定三元组\((time , pos , val)\)，然后分治：
外部以\(time\)进行排序，消除\(time\)的影响。 然后内部以\(pos\)为原则进行归并，然后怎么处理呢？ 考虑一下元素对答案的影响： 每次新增的点对此时答案的贡献为： （1）插入时间比它早，位置在它前面，值比它大的元素。 （2）插入时间比它早，位置在它后面，值比它大的元素。 所以我们先以\(pos\)从小到大归并排序好。 然后从前往后正着扫一遍， 如果元素的\(time \leq mid\)，那么在树状数组中插入它的\(val\)。 如果元素的\(time > mid\)，那么在树状数组中查询大于它的\(val\)的元素个数，加入答案。 然后再从后往前倒着扫一遍，处理方法一样。 这样我们最后就得到了每加入一个元素新增的贡献数，最后统计一下答案即可。 具体代码。例题4：
给定一个大小为\(n*n\)的矩阵，初始每个格子元素都为\(0\)
一共有\(10^5\)个操作，操作如下： （1）type=1：x y val ,把(x,y)位置的元素加上val。 （2）type=2：x1 y1 x2 y2, 查询(x1,y1)到(x2,y2)这个矩形的元素和。
貌似是上面的 例题1 的升级版....
由二维变为三维，怎么做呢？ 其实差不多。 二维前缀和之类的略，自己\(yy\)，然后： 建立三元组\((time , x , y)\) 会影响询问答案的为：操作时间早于其，x、y都小于等于它x、y的修改操作 所以外部以\(time\)排序，然后以\(x\)为原则归并。 归并的时候，如果是左边区间的修改操作，把其修改值\(val\)值插入树状数组中的\(y\)位置。 如果是右边的查询操作，查询树状数组中小于等于其\(y\)值的元素值之和。 这题做完了......C.\(CDQ\)分治的嵌套使用
1.解决四维偏序问题：
首先我们考虑三维偏序的解决方法：
外围排序三元组变为\([L,b,c]与[R,b',c']\)，然后归并变为\([L,L,c]与[R,R,c']\) 所以此时只需要在树状数组中查询\(c\)了。 那么四维是不是类似呢？ 首先外围排序，四元组变为\([L,b,c,d]与[R,b,c,d]\) 然后我们先以\(b\)为原则归并，但是并不统计答案。 此时我们要记录归并好的序列中每一个元素的\(a\)是属于\(L\)还是\(R\)。 那么此时只有\(b\)是有序的，\(a\)虽然无序但是我们记录了其来源（顺序）。 即此时的四元组为\([L/R,L,c,d]\)与\([L/R,R,c',d']\) 此时把这个新的序列带入下一层\(CDQ\)中再跑一遍，不就是三维偏序的处理吗？ 但是这里注意，为了保证\(a\)的顺序，只有\([L,L,c,d]\)与\([R,R,c',d']\)的元素才是合法的。 这个也非常好解决，第一层\(CDQ\)归并时对每个元素打一个标记即可。 具体的代码见2.解决N维偏序问题
这里提个醒，用嵌套\(CDQ\)解决\(N\)维偏序问题的复杂度是\(O(N\ log^{N-1}N)\)的。
其实搞懂了四维偏序的解决方法后，五维、六维....不是一样的吗？ 四维时我们打了一层标记，消除了一维的影响，最终变为了三维偏序问题。 那么\(N\)维我们则先归并\(N-3\)遍，打\(N-3\)层标记。 这样一共消除了\(N-3\)维的影响，然后再跑三维偏序即可。 实现五维偏序的具体代码见。一些非常优秀的题目(难度递增)：
（1）
（2） （3） （4） （5） （6） （7） （8） （9）