借鉴的第一篇题解

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+5,maxk=2e5+5;
struct node {
	int x,y,z,ans,w;
} a[maxn],b[maxn];
int n,cnt[maxk],t[maxk];
int k,n2;
bool cmpx(node u,node v) {
	if(u.x!=v.x)return u.x<v.x;
	if(u.y!=v.y)return u.y<v.y;
	return u.z<v.z;
}
bool cmpy(node u,node v) {
	if(u.y!=v.y)return u.y<v.y;
	return u.z<v.z;
}
int lowbit(int x) {
	return x&(-x);
}
void update(int x,int y) {
	while(x<maxk) {
		t[x]+=y;
		x+=lowbit(x);
	}
}
int sum(int x) {
	int ans=0;
	while(x>=0) {
		ans+=t[x];
		x-=lowbit(x);
	}
	return ans;
}
void cdq(int l,int r) {
	if(l==r)return;
	int mid=(l+r)>>1;
	cdq(l,mid);
	cdq(mid+1,r);
	sort(a+1,a+mid+1,cmpy);
	sort(a+mid+1,a+r+1,cmpy);
	int i=mid+1,j=l;
	while(i<=r) {
		while(a[j].y<=a[i].y && j<=mid) {
			update(a[j].z,a[j].w);
			j++;
		}
		a[i].ans+=sum(a[i].z);
		i++;
	}
	for(i=l; i<j; i++) {
		update(a[i].z,-a[i].w);
	}
}
signed main() {
	cin>>n2>>k;
	for(int i=1; i<=n2; i++) {
		cin>>b[i].x>>b[i].y>>b[i].z;
	}
	sort(b+1,b+n2+1,cmpx);
	int c=0;
	for(int i=1; i<=n2; i++) {
		c++;
		if(b[i].x!=b[i+1].x || b[i].y!=b[i+1].y || b[i].z!=b[i+1].z) {
			a[++n]=b[i];
			a[n].w=c;
			c=0;
		}
	}
	cdq(1,n);
	for(int i=1; i<=n; i++) {
		cnt[a[i].ans+a[i].w-1]+=a[i].w;
	}
	for(int i=0; i<n2; i++) {
		cout<<cnt[i]<<"\n";
	}
	return 0;
}

qwq

%%%