CDQ分治
用于解决三维偏序问题。
P3810 【模板】三维偏序 / 陌上花开
有 \(n\) 个元素，第 \(i\) 个元素有 \(a_i, b_i, c_i\) 三个属性，求满足 \(a_j \leq a_i\) 且 \(b_j \leq b_i\) 且 \(c_j \leq c_i\) 且 \(j \neq i\) 的 \(j\) 的数量。
我们可知一维偏序就是简单排序，二维偏序是求逆序对个数，可以推出三维偏序可以先给第一维排序，再把第二位归并排序，同时用树状数组维护第三维的贡献。
代码如下：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=2e5+10;
int k,tr[M],ans[N];
struct node{int a,b,c;int cnt,res;
}q[N],p[N];
bool cmp(node n,node m){if(n.a!=m.a) return n.a<m.a;if(n.b!=m.b) return n.b<m.b;return n.c<m.c;
}
int lowbit(int x){return x&(-x);
}
void add(int x,int w){while(x<=k){tr[x]+=w;x+=lowbit(x);}
}
int query(int x){int res=0;while(x){res+=tr[x];x-=lowbit(x);}return res;
}
void cdq(int l,int r){if(l>=r) return;int mid=(l+r)>>1;cdq(l,mid),cdq(mid+1,r);int i=l,j=mid+1,k=0;while(i<=mid&&j<=r){if(q[i].b<=q[j].b){add(q[i].c,q[i].cnt);p[++k]=q[i++];}else{q[j].res+=query(q[j].c);p[++k]=q[j++];}}while(i<=mid){add(q[i].c,q[i].cnt);p[++k]=q[i++];}while(j<=r){q[j].res+=query(q[j].c);p[++k]=q[j++];}for(int i=l;i<=mid;i++) add(q[i].c,-q[i].cnt);for(int i=l,j=1;j<=k;i++,j++) q[i]=p[j];
}
int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n,m=1;cin>>n>>k;for(int i=1;i<=n;i++){cin>>q[i].a>>q[i].b>>q[i].c;q[i].cnt=1,q[i].res=0;}sort(q+1,q+n+1,cmp);for(int i=2;i<=n;i++){if(q[i].a==q[m].a&&q[i].b==q[m].b&&q[i].c==q[m].c) q[m].cnt++;else q[++m]=q[i];}cdq(1,m);for(int i=1;i<=m;i++) ans[q[i].res+q[i].cnt-1]+=q[i].cnt;for(int i=0;i<n;i++) cout<<ans[i]<<"\n";return 0;
}