CDQ分治
定义：
\(CDQ\) 分治是一种思想而不是具体的算法，和 动态规划 类似，大致分为三类：
- 解决和点对有关的问题。
- \(1D\) 动态规划的优化转移
- 通过 \(CDQ\) 分治，将一些动态问题转化为静态问题。
解决和点对有关的问题：
这类问题类似于：
给定一个长度为 \(n\) 的序列，统计有一些特性的点对 \((i,j)\) 的数量，或者使 \((i,j)\) 对应的函数值最大
流程：
- 找到这个序列中点 \(mid\)
- 将所有点对分为三类： 都在中点左边，一左一右，都在中点右边
- 将 \((1,n)\) 这个序列拆成两个序列： \((1,mid)\) 和 \((mid+1,n)\) 。此时第一类点对和第三类点对都在这个序列。
- 递归处理这两类点对
- 设法处理一左一右的情况。
可以看出，\(CDQ\) 分治思想就是不断把点对通过递归的方式分给左右两个区间，运用 \(dfs(l,r)\) 这种函数解决问题。
例题：
最经典的就是处理三维偏序：陌上花开
题意：
有 \(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\) 的数量。
分析：
首先，数字顺序没有影响答案，因此可以重新进行排序，并且将相同的数字存一块。
按照 \(a\) 排列数组，则满足答案的式子为 \(b_j \leq b_i,c_j \leq c_i\)。
传到 \(solve\) 中后，我们把左右两边 \([l,mid],[mid+1,r]\) 分块按 \(b\) 排列。
然后从 \(i\in [mid+1,r]\) 中，挑选出 \(b_j \leq b_i\) 的情况，并且运用 树状数组 在 \(c_j\) 的位置上加上 \(c_j\) 的数量。
然后，计算 \(c_j \leq c_i\) 的数量一共有多少个。这个操作也是运用了树状数组。
最后，注意算完清空即可。更多详细过程在代码中：
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&-x
const int N=5e5+5;
struct node{
int a,b,c,cnt,ans;
}s1[N],s2[N];
int ans[N];
bool cmp1(node x,node y){//按照第一维排序
if(x.a==y.a){
if(x.b==y.b) return x.c<y.c;
else return x.b<y.b;
}
else return x.a<y.a;
}
bool cmp2(node x,node y){
if(x.b==y.b) return x.c<y.c;
else return x.b<y.b;
}
int n,k,m,cnt;
int c[N];
void add(int x,int z){
for(;x<=k;x+=lowbit(x)) c[x]+=z;
}
int query(int x){//记录权值为x的元素的个数
int res=0; for(;x;x-=lowbit(x)) res+=c[x]; return res;
}
void solve(int l,int r){
if(l==r) return;
int mid=l+r>>1;
solve(l,mid); solve(mid+1,r);
sort(s2+l,s2+mid+1,cmp2); sort(s2+mid+1,s2+r+1,cmp2);
//分区键排序：保证[l,mid] 第一维小于 [mid+1,r] 第一维，并且保证两区间内第二维单调不下降
int i,j=l;
for(i=mid+1;i<=r;i++){
while(s2[i].b>=s2[j].b&&j<=mid){
add(s2[j].c,s2[j].cnt);//在s2[j]加上s2[j]的个数，表示第二维满足
j++;
}
s2[i].ans+=query(s2[i].c);//查询[l,mid] 中有多少数满足小于等于s2[i].c
}
for(i=l;i<j;i++) add(s2[i].c,-s2[i].cnt);
}
int main(){
cin>>n>>k;
for(int i=1,x,y,z;i<=n;i++){
scanf("%d%d%d",&x,&y,&z); s1[i].a=x; s1[i].b=y; s1[i].c=z;
}
sort(s1+1,s1+1+n,cmp1);
for(int i=1;i<=n;i++){//转入 CDQ 数组
cnt++;
if((s1[i].a!=s1[i+1].a)||(s1[i].b!=s1[i+1].b)||(s1[i].c!=s1[i+1].c)){
s2[++m].a=s1[i].a,s2[m].b=s1[i].b,s2[m].c=s1[i].c; s2[m].cnt=cnt; cnt=0;
}
}
solve(1,m);
for(int i=1;i<=m;i++) ans[s2[i].ans+s2[i].cnt-1]+=s2[i].cnt;
//实际一个数的答案是和这个数相同的个数cnt和本身的答案ans
for(int i=0;i<n;i++) printf("%d\n",ans[i]);
system("pause");
return 0;
}
优化 \(1D\) 动态规划转移：
\(1D\) 动态规划指的是一类特定的 \(DP\) 问题，该类题目的特征是 \(DP\) 数组是一维的，转移是 \(O(n)\) 的。
而分治能把他们的时间复杂度下降到 \(O(n \log^2 n)\)
通常，这些 \(dp\) 条件是多维偏序。
流程：
- \(l=r\) 说明 \(dp_r\) 值已经被计算好了，直接令 \(dp_r+1\)
- 递归使用
solve(l,mid) - 处理所有 \(l\leq j \leq mid, mid+1\leq i \leq r\) 的转移关系
- 递归使用
solve(mid+1,r)
第三步做法和 \(CDQ\) 分治求三维偏序差不多。处理转移关系时，依然将所有点 \(i,j\) 按照 \(a\) 排序。然后跟上面处理差不多，最后查一下前缀最大值更新 \(dp_i\) 就可以了。
给一道例题：[SDOI2011]拦截导弹
动态问题转化为静态问题：
前两种情况使用分治目的是： 将序列折半，递归处理点对间的关系。
不过现在要求折半 时间序列。
它适用于一些「需要支持做 \(xxx\) 修改然后做 \(xxx\) 询问」的数据结构题。该类题目有两个特点：
- 把询问离线，所有操作会按时间排成一个序列。
- 每一个修改和之后的询问息相关，有 \(O(n^2)\) 对。
分治的操作和处理点对关系的分支操作也相同。
如果各个修改之间是 独立 的话，就不需要处理左右区间的时序问题。
如果不独立，那么两个区间可能会进行依赖关系，此时所有跨越 \(mid\) 的修改必须放在 solve(l,mid) 和 solve(mid+1,r) 之间。