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
| #include <bits/stdc++.h>
#define MAXN 200005
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
int rt[MAXN];
namespace SegmentTree{
struct node{
int l,r;
int val;
}tree[MAXN*150];
int tot;
#define lc tree[i].l
#define rc tree[i].r
inline void pushup(int i){
tree[i].val=tree[lc].val+tree[rc].val;
}
void Update(int &i,int pos,int val,int l,int r){
if (!i) i=++tot;
if (l==r){
tree[i].val+=val;
return ;
}
int mid=(l+r)>>1;
if (pos<=mid) Update(lc,pos,val,l,mid);
else Update(rc,pos,val,mid+1,r);
pushup(i);
}
int Query(int i,int L,int R,int l,int r){
if (L<=l&&r<=R){
return tree[i].val;
}
int mid=(l+r)>>1,ans=0;
if (L<=mid) ans+=Query(lc,L,R,l,mid);
if (mid<R) ans+=Query(rc,L,R,mid+1,r);
return ans;
}
}
using namespace SegmentTree;
struct Flower{
int a,b,c;
}f[MAXN];
inline bool operator < (const Flower &A,const Flower &B){
if (A.a!=B.a) return A.a<B.a;
else if (A.b!=B.b) return A.b<B.b;
return A.c<B.c;
}
#define lowbit(x) x&(-x)
int k;
inline void upd(int x,int y,int val){
for (register int i=x;i<=k;i+=lowbit(i)){
Update(rt[i],y,val,1,k);
}
}
inline int qry(int x,int y){
int ans=0;
for (register int i=x;i>0;i-=lowbit(i)){
ans+=Query(rt[i],1,y,1,k);
}
return ans;
}
int Ans[MAXN];
int main(){
int n=read();k=read();
for (register int i=1;i<=n;++i){
f[i].a=read(),f[i].b=read(),f[i].c=read();
}
sort(f+1,f+1+n);
int same=1;
for (register int i=1;i<=n;++i){
if (f[i+1].a==f[i].a&&f[i+1].b==f[i].b&&f[i+1].c==f[i].c){
same++;
}
else {
upd(f[i].b,f[i].c,same);
Ans[qry(f[i].b,f[i].c)]+=same;
same=1;
}
}
for (register int i=1;i<=n;++i){
printf("%d\n",Ans[i]);
}
}
|
