记录编号	600123	评测结果	AAAA
题目名称	陌上花开	最终得分	100
用户昵称	djyqjy	是否通过	通过
代码语言	C++	运行时间	0.660 s
提交时间	2025-04-16 12:50:39	内存使用	6.54 MiB

#include<bits/stdc++.h>
using namespace std;
const int N=100010,K=200010;
int n,k;
struct node
{
	int a,b,c;
	int cnt,ans;
}nodes[N],nd[N];
bool cmpA(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;
}
int m;
bool cmpB(node a,node b)
{
	if(a.b==b.b) return a.c<b.c;
	return a.b<b.b;
}
int c[K];
void add(int w,int x)
{
	while(w<=k)
	{
		c[w]+=x;
		w+=w&-w;
	}
	return;
}
int q(int w)
{
	int x=0;
	while(w)
	{
		x+=c[w];
		w-=w&-w;
	}
	return x;
}
void CDQ(int l,int r)
{
	if(l==r) return;
	int mid=(l+r)/2;
	CDQ(l,mid);
	CDQ(mid+1,r);
	sort(nd+l,nd+mid+1,cmpB);
	sort(nd+mid+1,nd+r+1,cmpB);
	int i=l,j=mid+1;
	while(j<=r)
	{
		while(i<=mid&&nd[i].b<=nd[j].b)
		{
			add(nd[i].c,nd[i].cnt);
			i++;
		}
		nd[j].ans+=q(nd[j].c);
		j++;
	}
	for(int x=l;x<i;x++)
		add(nd[x].c,-nd[x].cnt);
	return;
}
int ans[N];
int main()
{
	freopen("FlowerOpen.in","r",stdin);
	freopen("FlowerOpen.out","w",stdout);
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
		scanf("%d%d%d",&nodes[i].a,&nodes[i].b,&nodes[i].c);
	sort(nodes+1,nodes+1+n,cmpA);
	int jsq=0;
	for(int i=1;i<=n;i++)
	{
		jsq++;
		if(nodes[i].a!=nodes[i+1].a||nodes[i].b!=nodes[i+1].b||nodes[i].c!=nodes[i+1].c)
		{
			m++;
			nd[m].a=nodes[i].a;
			nd[m].b=nodes[i].b;
			nd[m].c=nodes[i].c;
			nd[m].cnt=jsq;
			jsq=0;
		}
	}
	CDQ(1,m);
	for(int i=1;i<=m;i++)
	    ans[nd[i].ans+nd[i].cnt-1]+=nd[i].cnt;
	for(int i=0;i<n;i++)
	    printf("%d\n",ans[i]);
	return 0;
}