定义
CDQ 分治作为一种思想，主要在解决形如 \([l,r]\) 区间中找符合要求的点对 \((i,j)\) 的问题时应用。具体的思想是：
- 先递归解决 \([l,mid]\) 和 \([mid+1,r]\) 中的点对；
- 再计算 \(l\le i\le mid<mid+1\le j\le r\) 的点对 \((i,j)\) 数量。
例题
例 1：P3810 【模板】三维偏序（陌上花开）
题意：给定长为 \(n\) 的数组 \(a,b,c\)，令 \(f(i)\) 表示 \(a_j\le a_i,b_j\le b_i,c_j\le b_i\) 的 \(j\) 的数量，对于每个 \(d\in[0,n)\)，求出满足 \(f(i)=d\) 的 \(i\) 的个数。
问题实质上可以转化为求出所有的 \(f(i)\)。对于 \(f(i)\)，我们一维一维处理：先按照 \(a\) 升序排序，这样我们就要找出所有满足 \(b_j\le b_i,c_j\le c_i\) 的有序数对 \((j,i)\)（\(j<i\)）的个数。对于剩下两维，我们使用 CDQ 分治。假设函数 cdq(l,r) 能够处理 \([l,r]\) 之间的问题，那么，算法流程如下：
- 先调用
cdq(l,mid)和cdq(mid+1,r)； - 计算 \(l\le i\le mid<mid+1\le j\le r\) 的点对 \((i,j)\) 数量。
现在考虑设计算法解决后一个问题。我们可以枚举每一个 \(j\in[mid+1,r]\)，计算符合条件的 \(i\)。先在 \([l,mid]\) 和 \([mid+1,r]\) 中分别按 \(b\) 排序，这样我们从小到大枚举 \(j\) 时，\(i\) 相对应的是 \([l,x]\) 的一段，且 \(x\) 随 \(j\) 增大而不降，这一点可以用双指针解决。然后我们要统计 \([l,x]\) 中 \(c_i<c_j\) 的个数，可以使用树状数组解决。
时间复杂度满足 \(T(n) = 2T(\frac{n}{2})+\mathcal{O}(n\log n)\)，于是时间复杂度 \(T(n)=\mathcal{O}(n\log^2 n)\)。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 100005
#define maxk 200005
using namespace std;
int n,k,ans[maxn],cnt[maxn],num[maxn]; struct node{int a,b,c,cnt,id;}a[maxn]; bool cmp2(node aa,node bb){return aa.b<bb.b;}
bool cmp1(node aa,node bb){return aa.a==bb.a?(aa.b==bb.b?aa.c<bb.c:aa.b<bb.b):aa.a<bb.a;}
int c[maxk]; int lowbit(int x){return x&(-x);} void modify(int p,int ad){for(;p<=k;p+=lowbit(p)) c[p]+=ad;}
int query(int p){int res=0; for(;p>=1;p-=lowbit(p)) res+=c[p]; return res;}
void cdq(int l,int r){
if(l==r) return; int mid=(l+r)>>1; cdq(l,mid); cdq(mid+1,r);
sort(a+l,a+mid+1,cmp2); sort(a+mid+1,a+r+1,cmp2); int i=l,j=mid+1;
for(;j<=r;j++){while(i<=mid&&a[i].b<=a[j].b) modify(a[i].c,a[i].cnt),i++; ans[a[j].id]+=query(a[j].c);}
for(i--;i>=l;i--) modify(a[i].c,-a[i].cnt);
}
int main(){
scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i].a,&a[i].b,&a[i].c),a[i].id=i; sort(a+1,a+1+n,cmp1);
int pos=1; for(int i=2;i<=n;i++){
if(a[i].a==a[i-1].a&&a[i].b==a[i-1].b&&a[i].c==a[i-1].c) a[pos].cnt++;
else{a[pos]=(node){a[i-1].a,a[i-1].b,a[i-1].c,++a[pos].cnt,pos}; num[pos]=a[pos].cnt; pos++;}
if(i==n){a[pos]=(node){a[n].a,a[n].b,a[n].c,++a[pos].cnt,pos}; num[pos]=a[pos].cnt;}
} cdq(1,pos); for(int i=1;i<=pos;i++) cnt[ans[i]+num[i]-1]+=num[i]; for(int i=0;i<n;i++) printf("%d\n",cnt[i]); return 0;
}