提交开火红花

#include<bits/stdc++.h>
#define maxn 100005
#define maxa 200005
using namespace std;

struct node{
	int a,b,c,w,id;
}dt[maxn],dt2[maxn];

bool cmp_abc(node L,node R){
	if(L.a!=R.a)return L.a<R.a;
	if(L.b!=R.b)return L.b<R.b;
	return L.c<R.c;
}

bool cmp_bc(node L,node R){
	if(L.b!=R.b)return L.b<R.b;
	return L.c<R.c;
}

int _n,n,k,tr[maxa],mine[maxn],emm[maxn],ans[maxn];

void add(int id,int val){
	for(;id<=k;id+=id&-id)tr[id]+=val;
}

int ask(int id){
	int ans=0;
	for(;id;id-=id&-id)ans+=tr[id];
	return ans;
}

void not_great_cdq(int l,int r){
	if(l==r)return;
	int mid=(l+r)/2,z=l;
	not_great_cdq(l,mid);
	not_great_cdq(mid+1,r);
	sort(dt2+l,dt2+mid+1,cmp_bc);
	sort(dt2+mid+1,dt2+r+1,cmp_bc);
	for(int i=mid+1;i<=r;i++){
		while(z<=mid&&dt2[z].b<=dt2[i].b){
			add(dt2[z].c,dt2[z].w);z++;
		}
		mine[dt2[i].id]+=ask(dt2[i].c);
	}
	for(int j=l;j<z;j++)add(dt2[j].c,-dt2[j].w);
}

int main(){
	cin>>_n>>k;
	for(int i=1;i<=_n;i++){
		cin>>dt[i].a>>dt[i].b>>dt[i].c;
	}
	sort(dt+1,dt+n+1,cmp_abc);
	for(int i=1;i<=_n;){
		dt2[n+1]=dt[i];dt2[n+1].w=1;i++;
		while(i<=_n&&dt[i].a==dt2[n+1].a&&dt[i].b==dt2[n+1].b&&dt[i].c==dt2[n+1].c){
			dt2[n+1].w++;i++;
		}
		n++;dt2[n].id=n;emm[n]=mine[n]=dt2[n].w;mine[n]--;
	}
	not_great_cdq(1,n);
	for(int i=1;i<=n;i++){
//		cout<<mine[i]<<' ';
		ans[mine[i]]+=emm[i];
	}
//	cout<<endl;
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}