记录编号	600115	评测结果	AAAA
题目名称	3336.陌上花开	最终得分	100
用户昵称	李奇文	是否通过	通过
代码语言	C++	运行时间	0.642 s
提交时间	2025-04-15 21:54:58	内存使用	6.57 MiB

#include<bits/stdc++.h>
using namespace std;
constexpr int N=1e5+10;
constexpr int K=2e5+10;
int n,k,m,t,res[N];
struct pt{
	int a,b,c;
	int cnt;
	int res;
	bool operator!=(pt o) const{
		if(a!=o.a) return true;
		if(b!=o.b) return true;
		if(c!=o.c) return true;
		return false;
	}
};
pt e[N],f[N];
struct treea{
	int g[K];
	int lowbit(int x){return (x&(-x));}
	void addt(int p,int v){
		while(p<=k){
			g[p]+=v;
			p+=lowbit(p);
		}
		return;
	}
	int askt(int p){
		int res=0;
		while(p){
			res+=g[p];
			p-=lowbit(p);
		}
		return res;
	}
}tr;
bool cmp1(pt x,pt y){
	if(x.a!=y.a) return x.a<y.a;
	if(x.b!=y.b) return x.b<y.b;
	return x.c<y.c;
}
bool cmp2(pt x,pt y){
	if(x.b!=y.b) return x.b<y.b;
	return x.c<y.c;
}
void cdq(int l,int r){
	if(l==r) return;
	int mid=(l+r)>>1;
	cdq(l,mid);
	cdq(mid+1,r);
	sort(f+l,f+mid+1,cmp2);
	sort(f+mid+1,f+r+1,cmp2);
	int i=l,j=mid+1;
	while(j<=r){
		while(i<=mid&&f[i].b<=f[j].b){
			tr.addt(f[i].c,f[i].cnt);
			i++;
		}
		f[j].res+=tr.askt(f[j].c);
		j++;
	}
	for(int k=l;k<i;k++) tr.addt(f[k].c,-f[k].cnt);
}
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",&e[i].a,&e[i].b,&e[i].c);
	sort(e+1,e+1+n,cmp1);
	f[++m]=e[1];
	f[m].cnt=1;
	for(int i=2;i<=n;i++)
		if(e[i].a!=e[i-1].a||e[i].b!=e[i-1].b||e[i].c!=e[i-1].c) f[++m]=e[i],f[m].cnt=1;
		else f[m].cnt++;
	cdq(1,m);
	for(int i=1;i<=m;i++){
		res[f[i].res+f[i].cnt-1]+=f[i].cnt;
	}
	for(int i=0;i<n;i++){
		printf("%d\n",res[i]);
	}
	return 0;
}