什么是CDQ分治啊（战术后仰）

所谓CDQ分治，就是以为叫做CDQ的大佬发明的分治算法，其灵感思路来源于归并排序（应该），用于解决静态的区间查询问题。

入门：逆序对，这其实是个二维偏序，逆序对的标准解法就是归并排序，其实就是CDQ分治，具体而言在前后两半都排好序后，查询后面的有多少比前面大，由于都是排好序的，所以时间复杂度线性，总复杂度O（nlogn）

#include<cstdio>
#include<iostream>
using namespace std;
int n,a[500010],c[500010];
long long ans;

void msort(int b,int e)//归并排序
{
    if(b==e)  
		return;
    int mid=(b+e)/2,i=b,j=mid+1,k=b;
    msort(b,mid),msort(mid+1,e);
    while(i<=mid&&j<=e)
    	if(a[i]<=a[j])
    		c[k++]=a[i++];
    	else
    		c[k++]=a[j++],ans+=mid-i+1;//统计答案
    while(i<=mid)
    	c[k++]=a[i++];
    while(j<=e)
    	c[k++]=a[j++];
    for(int l=b;l<=e;l++)
    	a[l]=c[l];
} 

int main()
{
    scanf("%d",&n); 
    for(int i=1;i<=n;i++)
    	scanf("%d",&a[i]);
    msort(1,n);
    printf("%lld",ans);
    return 0;
}

其实还有一种写法：用树状数组维护一个桶，从后往前遍历，对每个数查询比自己小的数有多少个即可，复杂度O（nlogn）

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int tree[500010],rank[500010],n;
long long ans; 
struct point
{
    int num,val;
}a[500010];
inline bool cmp(point q,point w)
{
    if(q.val==w.val)
        return q.num<w.num;
    return q.val<w.val;
}
inline void insert(int p,int d)
{
    for(;p<=n;p+=p&-p)
        tree[p]+=d; 
}
inline int query(int p)
{
    int sum=0;
    for(;p;p-=p&-p)
        sum+=tree[p];
    return sum;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i].val),a[i].num=i;
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++)
        rank[a[i].num]=i;
    for(int i=1;i<=n;i++)
    {
        insert(rank[i],1);
        ans+=i-query(rank[i]);
    }
    printf("%lld",ans);
    return 0;
} 

这里提到树状数组解逆序对其实是为后面一道例题做铺垫

那么开始正经例题：三维偏序

三维偏序可以用很多方法做：KD-Tree，树状数组套线段树，CDQ分治等等

OIwiki上说树套树最基础的是线段树套平衡树

例题：P3810

首先我们将第一维排序，在此基础上对第二维进行归并排序，在排序过程中，因为第一维是有序的，因此如果 $b_j$ < $b_i$ 的话，我们就可以将 $c_j$放入树状数组中，因为此时只要 $c_j$ < $c_i$ 的话，这就是一个符合条件的三维偏序，每次如果发现比$b_i$小的$b_j$都添加完了的话，就统计比$c_i$小的部分，参考前面的树状数组解逆序对。

还有几个要注意的：

1. 要去重，因为不去重的话相同的数贡献不到，去重后要记得相同的要相互贡献
2. 注意最后统计的数$f_i$=$d$的个数
3. 不要把$k$写成$n$（只有我一个会犯这样的错误还调了两天吧，悲

#include<bits/stdc++.h>
#define N 1000010
using namespace std;
long long c[N],ans[N],dui[N],bac[N];
long long n,cnt,nothing;
struct node{
	long long a,b,c,tot,id;
}pt[N],m[N];
inline long long lowbit(long long x) {return x-=(x&(x-1));}
inline void updata(long long x,long long val) {while(x<=nothing) c[x]+=val,x+=lowbit(x);}
inline void clean(long long x) {while(x<=nothing) c[x]=0,x+=lowbit(x);}
inline long long sum(long long x) {
	long long ans=0;
	while(x>0) ans+=c[x],x-=lowbit(x);
	return ans;
}
bool cmp(node a1,node a2) {
	if(a1.a==a2.a) {
		if(a1.b==a2.b) {
			if(a1.c==a2.c) return a1.id<a2.id;
			return a1.c<a2.c;
		} return a1.b<a2.b;
	} return a1.a<a2.a;
}
bool cmp2(node a1,node a2) {
	if(a1.b==a2.b) {
		if(a1.a==a2.a) {
			if(a1.c==a2.c) return a1.id<a2.id;
			return a1.c<a2.c;
		} return a1.a<a2.a;
	} return a1.b<a2.b;
}
void cdq(long long l,long long r) {
	if(l>=r) return ;
	long long mid=(l+r)/2;
	cdq(l,mid),cdq(mid+1,r),sort(m+l,m+mid+1,cmp2),sort(m+mid+1,m+r+1,cmp2);
	long long ll=l,rr=mid+1;
	while(ll<=mid&&rr<=r) {
		if(m[ll].b<=m[rr].b) updata(m[ll].c,m[ll].tot),ll++;
		else ans[m[rr].id]+=sum(m[rr].c),rr++;
	}
	while(rr<=r) ans[m[rr].id]+=sum(m[rr].c),rr++;
	for(int i=l; i<=r; i++) clean(m[i].c);
}
int main()
{
//	freopen("NOTE 3810.out","w",stdout);
	cin>>n>>nothing;
	for(long long i=1; i<=n; i++) cin>>pt[i].a>>pt[i].b>>pt[i].c;
	sort(pt+1,pt+n+1,cmp),cnt=0;
	for(int i=1; i<=n; i++) {
		if(pt[i].a!=pt[i-1].a||pt[i].b!=pt[i-1].b||pt[i].c!=pt[i-1].c) m[++cnt]=pt[i],m[cnt].id=cnt,m[cnt].tot=0;
	    m[cnt].tot++;
	}
	cdq(1,cnt);
	for(long long i=1; i<=cnt; i++) bac[ans[m[i].id]+m[i].tot-1]+=m[i].tot;
	for(long long i=0; i<n; i++) cout<<bac[i]<<endl;
	return 0;
}

题外话（或许不是题外话）：树状数组的模板可以用CDQ分治来解

把一个个修改操作和查询操作放在一起按端点排序，最后对操作进行CDQ分治即可，具体看代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,qn;
ll ans[500010],an;

struct query {
	ll idx,value,type;
};
query q[2000010],tmp[2000010];
bool operator< (query a1,query a2) {
	return a1.idx==a2.idx?a1.type<a2.type:a1.idx<a2.idx;
}
void cdq(ll l,ll r) {
	if(r-l<=1) return ;
//	cout<<1<<endl;
	ll mid=(l+r)/2;
	cdq(l,mid),cdq(mid,r);
	ll p1=l,p2=mid,tn=0,sum=0;
	while(p1<mid&&p2<r) {
		if(q[p1]<q[p2]) {
			if(q[p1].type==1) sum+=q[p1].value;
			tmp[tn++]=q[p1++];
		} else {
			if(q[p2].type==2) ans[q[p2].value]-=sum;
			if(q[p2].type==3) ans[q[p2].value]+=sum;
			tmp[tn++]=q[p2++];
		}
	}
	while(p1<mid) tmp[tn++]=q[p1++];
	while(p2<r) {
		if(q[p2].type==2) ans[q[p2].value]-=sum;
		if(q[p2].type==3) ans[q[p2].value]+=sum;
		tmp[tn++]=q[p2++];
	}
	for(ll i=0; i<tn; i++) q[i+l]=tmp[i];
}
int main() {
//	freopen("P3374_2.in","r",stdin);
	cin>>n>>m;
	for(ll i=1; i<=n; i++) {
		cin>>q[qn].value;
		q[qn].idx=i,q[qn++].type=1;
	}
	for(ll i=1; i<=m; i++) {
		ll ty;
		cin>>ty;
		if(ty==1) {
			cin>>q[qn].idx>>q[qn].value;
			q[qn++].type=1;
		}
		if(ty==2) {
			ll l,r;
			cin>>l>>r;
			q[qn].idx=l-1,q[qn].value=an,q[qn++].type=2;
			q[qn].idx=r,q[qn].value=an++,q[qn++].type=3;
		}
		
	}
	cdq(0,qn);
	for(ll i=0; i<an; i++) cout<<ans[i]<<endl;
	return 0;
}

CDQ大巨