我觉得呢，cdq的本质就是在归并排序消掉一维的影响来处理多维偏序问题。既然本质跟二分有关，那很容易猜到cdq处理k维偏序的时间复杂度为\(O(Nlog^{k-1}N)\)
三维偏序问题：形如：$求满足条件a_i<a_j,b_i<b_j,c_i<c_j且 \(j !=i\) 的 j 个数
比较常考的就是三维偏序，一般做法就是sort消掉一维的影响，cdq消掉一维的影响，在用树状数组维护前缀和来完成。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+107;
int n,k;
int b[N],s[N],f[N];
int read()
{
int f=1,s=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+(ch^48);ch=getchar();}
return f*s;
}
struct lmy
{
int x,y,z,id;
}a[N];
bool comp1(lmy a,lmy b)
{
if(a.x!=b.x) return a.x<b.x;
if(a.y!=b.y) return a.y<b.y;
return a.z<b.z;
}
bool comp2(lmy a,lmy b)
{
if(a.y!=b.y) return a.y<b.y;
if(a.z!=b.z) return a.z<b.z;
return a.x<b.x;
}
struct tree_array
{
int c[N];
int lowbit(int x){return x&(-x);}
void add(int x,int val)
{
while(x<=k)
{
c[x]+=val;
x+=lowbit(x);
}
}
int sum(int x)
{
int ans=0;
while(x)
{
ans+=c[x];
x-=lowbit(x);
}
return ans;
}
}Q;
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+r+1,comp2);
for(int i=l;i<=r;i++)
{
if(a[i].x<=mid) Q.add(a[i].z,1);
else s[a[i].id]+=Q.sum(a[i].z);
}
for(int i=l;i<=r;i++) if(a[i].x<=mid) Q.add(a[i].z,-1);
}
int main()
{
n=read(),k=read();
for(int i=1;i<=n;i++)
{
a[i].x=read(),a[i].y=read(),a[i].z=read();
a[i].id=i;
}
sort(a+1,a+1+n,comp1);
int i=1;
while(i<=n)
{
int j=i+1;
while(j<=n&&a[j].x==a[i].x&&a[j].y==a[i].y&&a[j].z==a[i].z)
j++;
while(i<j)
b[a[i].id]=a[j-1].id,i++;
}
for(int i=1;i<=n;i++) a[i].x=i;
cdq(1,n);
for(int i=1;i<=n;i++) f[s[b[a[i].id]]]++;
for(int i=0;i<n;i++) printf("%d\n",f[i]);
}
至于更多维的偏序问题，我们就可以cdq套cdq套cdq……
标签：偏序,ch,int,分治,消掉,cdq,一维 From： https://www.cnblogs.com/zhengchenxi/p/18357478