cdq（陈丹琦）分治，是一种类似二分的算法。基本思想同分治：
- 递归，把大问题划分成若干个结构相同的子问题，直到(L==R)；
- 处理左区间[L,mid]对右区间[mid+1,R]的影响；
- 合并。
它可以顶替复杂的高级数据结构，但必须离线操作。
N维偏序，就是求N个关键字下的顺/逆序对。cdq分治是这类题中常用的降维手段。
一维偏序
学习归并排序时，我们了解到它的一个特性就是可以用来求逆序对。
void merge(int L,int R) {
if(L == R)return;
int mid = (L+R)/;
merge(L,mid);
merge(mid+,R);
int idx = L;
int i = L,j = mid+;
while(i <= mid&&j <= R) {
if(a[i] <= a[j])temp[idx++] = a[i++];
else {
temp[idx++] = a[j++];
cnt += mid-i+;
}
}
while(i <= mid)temp[idx++] = a[i++];
while(j <= R)temp[idx++] = a[j++];
for(int i = L; i <= R; i++)
a[i] = temp[i];
}归并排序求逆序对
考虑它的原理：只统计对于右面的每一个元素，左边比它大的。
两边的数列都为有序，且各自的逆序对都已经统计完了。
那么对于右边的第j个元素（j>=mid+1），如果左边的第i个元素比j大，那么i+1,i+2....到mid一定都比j大。
这里就体现了cdq分治的思想，也是多维偏序的基础。可以说，归并排序求逆序对是cdq分治的一个特例。
二维偏序
除了归并排序，一维偏序也可以用树状数组解决。实际上，一部分树状数组能解决的问题，cdq分治也可以解决。
#include<iostream>
#include<cstdio>
#include<cstring>
#define MogeKo qwq
using namespace std;
const int maxn = ;
int n,m,opt,x,y,sum[maxn]; int lowbit(int x){
return x & -x;
} void update(int x,int k){
while(x <= n){
sum[x] += k;
x += lowbit(x);
}
} int query(int x){
int ans = ;
while(x){
ans += sum[x];
x -= lowbit(x);
}
return ans;
} int main(){
scanf("%d%d",&n,&m);
for(int i = ;i <= n;i++){
scanf("%d",&y);
update(i,y);
}
for(int i = ;i <= m;i++){
scanf("%d%d%d",&opt,&x,&y);
if(opt == )update(x,y);
if(opt == )printf("%d\n",query(y)-query(x-));
}
return ;
}
树状数组
树状数组板子题，可以轻松解决。
把它转化为二维偏序问题，对于每个修改和询问，都有（时间，位置）两个维度。
开一个结构体q[]，数组下标记录时间，q[].id记录位置，q[].type记录类型（修改或询问）。注意，当修改和询问在同一位置时，修改操作要优先。
解决二维偏序问题首先需要控制一维有序，另一维进行归并排序。在这里，时间默认就是有序的（++cnt）；
对于每个修改操作，记录修改的元素位置。数组赋初值的方式和修改操作相同，可以当做时间在最前的修改。
查询怎么办？用树状数组求一段区间和时，需要用到前缀和，即 R-(L-1)。
那么，询问的位置也可以拆分成两个：(L-1)和 R。用不同的type来区分它们：( L-1的要减去，R的要加上）。
如何进行归并排序？对于一段位置有序的区间，一定是时间在前的修改操作会影响时间在后的查询操作。
用sum维护区间内修改操作的值，修改时用sum+修改值；
用ans记录询问的答案，ans -所有(L-1)的sum +所有R的sum 即为这个询问的结果。为啥非要用cdq分治啊麻烦死了QAQ！！！
#include<iostream>
#include<cstdio>
#include<cstring>
#define MogeKo qwq
using namespace std;
const int maxn = *; int n,m,cnt,cqry,opt,x,y,ans[maxn];
struct node{
int type,id,val;
bool operator < (const node & x) const{
if(id != x.id)return id < x.id;
else return type < x.type;
}
}q[maxn],tem[maxn]; void cdq(int L,int R){
if(L == R) return;
int mid = L+R>>;
cdq(L,mid),cdq(mid+,R);
int t1 = L,t2 = mid+;
int sum = ;
for(int i = L;i <= R;i++){
if( (t1 <= mid && q[t1]<q[t2]) || t2 > R){
if(q[t1].type == ) sum += q[t1].val;
tem[i] = q[t1++];
}
else{
if(q[t2].type == ) ans[q[t2].val] -= sum;
if(q[t2].type == ) ans[q[t2].val] += sum;
tem[i] = q[t2++];
}
}
for(int i = L;i <= R;i++) q[i] = tem[i];
} int main(){
scanf("%d%d",&n,&m);
for(int i = ;i <= n;i++){
cnt++;
scanf("%d",&y);
q[cnt].type = ;
q[cnt].id = i;
q[cnt].val = y;
}
for(int i = ;i <= m;i++){
scanf("%d%d%d",&opt,&x,&y);
if(opt == ){
q[++cnt].type = ;
q[cnt].id = x;
q[cnt].val = y;
}
if(opt == ){
cqry++;
q[++cnt].type = ;
q[cnt].id = x-;
q[cnt].val = cqry;
q[++cnt].type = ;
q[cnt].id = y;
q[cnt].val = cqry;
}
}
cdq(,cnt);
for(int i = ;i <= cqry;i++)
printf("%d\n",ans[i]);
return ;
}
二维偏序
三维偏序
扩展到三维。设三维分别为x,y,z
先按x排序，消除第一维的影响。
考虑不使用cdq，用一个树状数组维护第二维，另一个树状数组维护第三维...就会出现树套树的神奇情况
模仿之前的做法，第二维使用cdq分治，按y进行归并排序。虽然x的顺序被打乱了，但左一半一定小于右一半。第二维的影响被消除了。
第三维可以用一个权值树状数组维护。
int t1=L, t2=mid+;
while(t2 <= R){
while(t1 <= mid && b[t1].y <= b[t2].y){
tree.update(b[t1].z,b[t1].num);
t1++;
}
b[t2].ans += tree.query(b[t2].z);
t2++;
}
已经控制x>x，将所有y<y时按z把当前花的个数加入树状数组，再查询比z小的在树状数组中有多少个。
由于归并排序时，y后的y一定大于y所以已经加入的z的个数不用清空。
当归并的操作结束时，再把树状数组减去已经加入的左区间的z的个数（也就是左区间指针t1之前）。
提供的数据中，可能有xyz完全相同的情况，所以初始化时要先去重，但不能直接调用unique函数。统计相同的花的个数，用结构体的.num记录。
这样当把花按x加入树状数组时，加入.num中的个数就可以了。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MogeKo qwq
using namespace std;
const int maxn = ;
int n,m,k,cnt[maxn]; struct node{
int x,y,z,num,ans;
bool operator < (const node & A) const {
return x<A.x || (x==A.x && (y<A.y || (y==A.y && z<A.z)));
}
bool operator == (const node & A) const {
return x==A.x && y==A.y && z==A.z;
}
}a[maxn],b[maxn]; bool cmpyz(node A,node B){
return A.y<B.y || (A.y==B.y && A.z<B.z);
} struct BIT{
int sum[maxn],len;
int lowbit(int x){
return x & -x;
}
void update(int x,int k){
for(int i = x; i<=len; i+=lowbit(i))
sum[i] += k;
}
int query(int x){
int ans = ;
for(int i = x; i; i-=lowbit(i))
ans += sum[i];
return ans;
}
}tree; void cdq(int L,int R){
if(L == R)return;
int mid = L+R>>;
cdq(L,mid),cdq(mid+,R);
sort(b+L,b+mid+,cmpyz);
sort(b+mid+,b+R+,cmpyz);
int t1=L, t2=mid+;
while(t2 <= R){
while(t1 <= mid && b[t1].y <= b[t2].y){
tree.update(b[t1].z,b[t1].num);
t1++;
}
b[t2].ans += tree.query(b[t2].z);
t2++;
}
for(int i = L;i <= t1-;i++)
tree.update(b[i].z,-b[i].num);
} int main(){
scanf("%d%d",&n,&k);
tree.len = k;
for(int i = ;i <= n;i++)
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
sort(a+,a+n+);
int bcnt = ;
for(int i = ;i <= n;i++){
bcnt++;
if(a[i]==a[i+])continue;
b[++m] = a[i], b[m].num = bcnt;
bcnt = ;
}
cdq(,m);
for(int i = ;i <= m;i++)
cnt[b[i].ans+b[i].num-] += b[i].num;
for(int i = ;i <= n-;i++)
printf("%d\n",cnt[i]);
return ;
}
三维偏序
其实cdq分治我也不是很明白qwq
理论上，cdq分治可以解决任意N维偏序问题。但是，cdq套cdq的复杂度会达到n logn，当它超过n的时候...还是选择暴力枚举吧w