记录编号	586601	评测结果	AAAA
题目名称	陌上花开	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.624 s
提交时间	2024-02-17 17:55:40	内存使用	18.62 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
//CDQ分治 
const int N = 1e5+10,M = 2e5+10;
int n,k,m;
struct made{
	int a,b,c,s,cnt;
}a[N],c[N];
bool cmp1(made x,made 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(made x,made y){
	if(x.b != y.b)return x.b < y.b;
	return x.c < y.c;
}
struct BIT{
	int c[M];
	int lowbit(int x){return (x & (-x));}
	void add(int x,int val){
		for(;x <= k;x += lowbit(x))c[x] += val;
	}
	int ask(int x){
		int ans = 0;
		for(;x > 0;x -= lowbit(x))ans += c[x];
		return ans;
	}
}t;
int ans[N];
void CDQ(int l,int r){
	if(l == r)return;
	int mid = l + r >> 1;
	CDQ(l,mid),CDQ(mid+1,r);
	sort(c+l,c+mid+1,cmp2);
	sort(c+mid+1,c+r+1,cmp2);
	int i = l,j = mid + 1;
	while(j <= r){
		while(i <= mid && c[i].b <= c[j].b)t.add(c[i].c,c[i].cnt),i++;
		c[j].s += t.ask(c[j].c);
		j++;
	}
	for(int u = l;u < i;u++)t.add(c[u].c,-c[u].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",&a[i].a,&a[i].b,&a[i].c);
	sort(a+1,a+1+n,cmp1);
	c[++m] = a[1];c[m].cnt = 1;
	for(int i = 2;i <= n;i++)
		if(a[i].a != a[i-1].a || a[i].b != a[i-1].b || a[i].c != a[i-1].c)c[++m] = a[i],c[m].cnt = 1;
		else c[m].cnt++;
	//离散化 
	CDQ(1,m);
	for(int i = 1;i <= n;i++)ans[c[i].s + c[i].cnt - 1] += c[i].cnt;
	for(int i = 0;i < n;i++)printf("%d\n",ans[i]);

	return 0;
	
}