1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
|
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
long long read()
{
long long x=0,f=1; char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
while(isdigit(c)){x=x*10+c-'0';c=getchar();}
return x*f;
}
const int N=100000+100;
const int M=200000+100;
struct node
{
int x,y,z,no,ans;
friend bool operator == (node a,node b)
{
return (a.x==b.x and a.y==b.y and a.z==b.z);
}
}nd[N];
bool cmp(node a,node b)
{
if(a.x==b.x)
{
if(a.y==b.y)
return a.z<b.z;
return a.y<b.y;
}
return a.x<b.x;
}
bool cmp2(node a,node b)
{
if(a.y==b.y) return a.z<b.z;
return a.y<b.y;
}
struct SegmentTree
{
#define lson (now<<1)
#define rson (now<<11)
#define mid ((now_l+now_r)>>1)
int sum[M<<2];
inline void update(int now)
{
sum[now]=sum[lson]+sum[rson];
}
void Add(int x,int v,int now,int now_l,int now_r)
{
if(now_l==now_r)
{
sum[now]+=v;
return ;
}
if(x<=mid) Add(x,v,lson,now_l,mid);
else Add(x,v,rson,mid+1,now_r);
update(now);
}
int Query(int l,int r,int now,int now_l,int now_r)
{
if(now_l>=l and now_r<=r)
return sum[now];
int t_ans=0;
if(l<=mid) t_ans+=Query(l,r,lson,now_l,mid);
if(r>mid) t_ans+=Query(l,r,rson,mid+1,now_r);
return t_ans;
}
#undef lson
#undef rson
#undef mid
}sgt;
int n,m,K,belong[N],cnt[N],ans[N],cnt_belong,ans2[N];
void CDQ(int l,int r)
{
if(l==r) return;
int mid=(l+r)/2;
CDQ(l,mid);
CDQ(mid+1,r);
int ptl=l;
for(int i=mid+1;i<=r;i++)
{
for(;nd[ptl].y<=nd[i].y and ptl<=mid;ptl++)
sgt.Add(nd[ptl].z,cnt[nd[ptl].no],1,0,K);
ans[nd[i].no]+=sgt.Query(0,nd[i].z,1,0,K);
}
ptl=l;
for(int i=mid+1;i<=r;i++)
for(;nd[ptl].y<=nd[i].y and ptl<=mid;ptl++)
sgt.Add(nd[ptl].z,-cnt[nd[ptl].no],1,0,K);
sort(nd+l,nd+r+1,cmp2);
}
int main()
{
n=read(),K=read();
for(int i=1;i<=n;i++)
nd[i].x=read(),nd[i].y=read(),nd[i].z=read(),nd[i].no=i;
sort(nd+1,nd+1+n,cmp);
for(int i=1;i<=n;i++)
if(nd[i]==nd[i-1])
cnt[cnt_belong]++,belong[nd[i].no]=cnt_belong;
else
cnt[++cnt_belong]++,belong[nd[i].no]=cnt_belong;
for(int i=1;i<=cnt_belong;i++)
ans[i]+=cnt[i]-1;
m=unique(nd+1,nd+1+n)-nd-1;
for(int i=1;i<=m;i++)
nd[i].no=i;
CDQ(1,m);
for(int i=1;i<=n;i++)
ans2[ans[belong[i]]]++;
for(int i=0;i<n;i++)
printf("%d\n",ans2[i]);
return 0;
}
|
