记录编号	567298	评测结果	AAAA
题目名称	陌上花开	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	0.644 s
提交时间	2021-11-26 13:43:34	内存使用	15.33 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
using namespace std;
const int maxn = 200005;
struct node {
	int x,y,z,num,ans;
	node() {
		x = y = z = num = ans = 0;
	}
	node(int x,int y,int z):x(x),y(y),z(z){}
}a[maxn],s[maxn],b[maxn];
int read() {
	int s = 0,f = 1;
	char c = getchar();
	for(;!isdigit(c);c = getchar());
	for(;isdigit(c);c = getchar())s = (s << 1) + (s << 3) + (c ^ '0');
	return s * f;
}
void write(int x) {
	if(x > 9)write(x / 10);
	putchar(x % 10 + '0');
	return ;
}
void print(int x) {
	write(x);
	putchar('\n');
	return ;
}
int lowbit(int x) {
	return x & -x;
}
int c[maxn];
int n,k,cnt,f[maxn];
void add(int x,int y) {
	for(;x <= k;x += lowbit(x))c[x] += y;
	return ;
} 
int query(int x) {
	int ans = 0;
	for(;x;x -= lowbit(x))ans += c[x];
	return ans;
}
bool cmp1(node p,node q) {
	return p.x == q.x ? (p.y == q.y ? p.z < q.z : p.y < q.y) : p.x < q.x;
}
bool cmp2(node p,node q) {
	return p.y == q.y ? p.z < q.z : p.y < q.y;
}
void solve(int l,int r) {
	if(l == r)return ;
	int mid = l + r >> 1;
	solve(l , mid);
	solve(mid + 1 , r);
	int i = l,j = mid + 1;
	for(int k = l;k <= r;++ k) {
	    if(j > r||(i <= mid&&a[i].y <= a[j].y)) {
	        add(a[i].z , a[i].num);
	        b[k] = a[i ++];
        }
        else {
            a[j].ans += query(a[j].z);
            b[k] = a[j ++];
        }
    }
    for(i = l;i <= mid;++ i)add(a[i].z , -a[i].num);
    for(int k = l;k <= r;++ k)a[k] = b[k];
	return ;
}
int main() {
    freopen("FlowerOpen.in","r",stdin);
    freopen("FlowerOpen.out","w",stdout);
	n = read();
	k = read();
	for(int i = 1;i <= n;++ i) {
		s[i].x = read(),s[i].y = read(),s[i].z = read();
	}
	sort(s + 1 , s + 1 + n , cmp1);
	int tot = 0;
	for(int i = 1;i <= n;++ i) {
		++ tot;
		if(s[i].x != s[i + 1].x||s[i].y != s[i + 1].y||s[i].z != s[i + 1].z) {
		    ++ cnt;
			a[cnt].x = s[i].x;
			a[cnt].y = s[i].y;
			a[cnt].z = s[i].z;
			a[cnt].ans = 0;
			a[cnt].num = tot;
			tot = 0;
		}
	}
	solve(1 , cnt);
	for(int i = 1;i <= cnt;++ i)f[a[i].num + a[i].ans - 1] += a[i].num;
	for(int i = 0;i < n;++ i) {
		print(f[i]);
	}
	return 0;
}