经典CDQ分治题，求三维偏序
#include<cstdio>
#include<algorithm>
using namespace std;const int maxn=200000+200;struct Node{
int a,b,c;int num,level;
}node[maxn];bool cmp(Node A,Node B){
if(A.a==B.a&&A.b==B.b) return A.c<B.c;if(A.a==B.a) return A.b<B.b;return A.a<B.a;
}bool cmpcdq(Node A,Node B){
if(A.b==B.b) return A.c<B.c;return A.b<B.b;
}int tree[maxn],color[maxn];
int ans[maxn];
int type;
int n,k;
int tot;inline int lowbit(int x){
return x&(-x);
} void Add(int ind,int v){
while(ind<=k){
if(color[ind]!=type) tree[ind]=0;color[ind]=type;tree[ind]+=v;ind+=lowbit(ind);}
}int getSum(int ind){
int sum=0;while(ind>0){
if(color[ind]==type) sum+=tree[ind];ind-=lowbit(ind);}return sum;
}void CDQ(int l,int r){
if(l==r) return ;int mid=(l+r)>>1;CDQ(l,mid);CDQ(mid+1,r);sort(node+l,node+mid+1,cmpcdq);sort(node+mid+1,node+r+1,cmpcdq);int i=l;int j=mid+1;type++;for(;j<=r;j++){
for(;node[i].b<=node[j].b&&i<=mid;i++) Add(node[i].c,node[i].num);node[j].level+=getSum(node[j].c); }
}int main(){
scanf("%d%d",&n,&k);for(int i=1;i<=n;i++){
int a,b,c;scanf("%d%d%d",&a,&b,&c);node[i]=Node{
a,b,c,1,0};}sort(node+1,node+n+1,cmp);tot=1;for(int i=2;i<=n;i++){
if(node[i].a==node[tot].a&&node[i].b==node[tot].b&&node[i].c==node[tot].c) node[tot].num++;else node[++tot]=node[i];}CDQ(1,tot);for(int i=1;i<=tot;i++) ans[node[i].num+node[i].level-1]+=node[i].num;for(int i=0;i<n;i++) printf("%d\n",ans[i]);
}