CDQ80pts求条 WA on#7#10

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5e5+10;
const ll MOD=1e9+7;
const ll inf=0x3f3f3f3f3f3f3f3f;
ll n,K,f[N],ans[N],tr[N];
struct node{
	ll a,b,c,id;
	bool operator<(const node x)const {
		if(a!=x.a)return a<x.a;
		if(b!=x.b)return b<x.b;
		if(c!=x.c)return c<x.c;
		return id<x.id;
	}
	bool operator==(const node x)const {
		return a==x.a&&b==x.b&&c==x.c;
	}
}x[N],y[N];
bool smer(node x,node y){
	if(x.b!=y.b)return x.b<y.b;
	if(x.c!=y.c)return x.c<y.c;
	return x.id<y.id;
}
ll lowbit(ll x){
	return x&(-x);
}
void add(ll idx,ll x){
	for(int i=idx;i<=n;i+=lowbit(i)){
		tr[i]+=x;
	}
	return ;
}
ll query(ll idx){
	ll sum=0;
	for(int i=idx;i>=1;i-=lowbit(i)){
		sum+=tr[i];
	}
	return sum;
}
void cdq(ll l,ll r){
	if(l==r)return ;
	ll mid=(l+r)/2;
	cdq(l,mid);
	cdq(mid+1,r);
	ll i=l,j=mid+1;
	for(int k=l;k<=r;k++){
		if(i<=mid&&(j>r||smer(x[i],x[j]))){
			add(x[i].c,1);
			y[k]=x[i];
			i++;
			
		}else{
			f[x[j].id]+=query(x[j].c);
			y[k]=x[j];
			j++;
		}
	}
	for(int k=l;k<=mid;k++){
		add(x[k].c,-1);
	}
	for(int k=l;k<=r;k++){
		x[k]=y[k];
	}
	return ;
}
int main(){
	cin>>n>>K;
	for(int i=1;i<=n;i++){
		cin>>x[i].a>>x[i].b>>x[i].c;
	}
	sort(x+1,x+1+n);
	for(int i=1;i<=n;i++)x[i].id=i;
	cdq(1,n);
	sort(x+1,x+1+n);
	for(int i=n;i>=1;i--){
		if(x[i]==x[i+1])f[i]=f[i+1];
		ans[f[i]]++;
	}
	for(int i=0;i<n;i++){
		cout<<ans[i]<<"\n";
	}
    return 0;
}