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
| #include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct node {
int a,b,c,w,ans;
} q[100005],q1[100005];
int c[200005];
int t[100005];
int n,nn,k;
inline int read() {
int sum=0;char ch=0;
while ((ch>'9' || ch<'0')&&(ch!='-')) ch=getchar();
while (ch>='0' && ch<='9') sum=sum*10+ch-'0',ch=getchar();
return sum;
}
bool cmp(node A,node B) {
if (A.a!=B.a) return A.a<B.a;
if (A.b!=B.b) return A.b<B.b;
return A.c<B.c;
}
inline int lowbit(int x) {return x&(-x);}
inline void update(int x,int val) {
for (;x<=k;x+=lowbit(x)) c[x]+=val;
}
inline int getsum(int x) {
int sum=0;
for (;x>0;x-=lowbit(x)) sum+=c[x];
return sum;
}
inline void clear(int x) {
for (;x<=k;x+=lowbit(x)) {
if (!c[x]) break;
c[x]=0;
}
}
void cdq(int l,int r) {
if (l==r) return;
int mid=(l+r)>>1;
cdq(l,mid);cdq(mid+1,r);
int s1=l,s2=mid+1,s3=l-1;
while (s1<=mid && s2<=r) {
if (q[s1].b<=q[s2].b) {
update(q[s1].c,q[s1].w);
q1[++s3]=q[s1];s1++;
}
else {
q[s2].ans+=getsum(q[s2].c);
q1[++s3]=q[s2];s2++;
}
}
while (s1<=mid) q1[++s3]=q[s1],s1++;
while (s2<=r) {
q[s2].ans+=getsum(q[s2].c);
q1[++s3]=q[s2],s2++;
}
for (int i=l;i<=r;i++) {
clear(q1[i].c);
q[i]=q1[i];
}
}
int main() {
n=read();read();
for (int i=1;i<=n;i++) {
q1[i].a=read();q1[i].b=read();q1[i].c=read();
k=max(k,q1[i].c);
}
sort(q1+1,q1+n+1,cmp);
int cnt=0;
for (int i=1;i<=n;i++) {
cnt++;
if (q1[i].a!=q1[i+1].a || q1[i].b!=q1[i+1].b || q1[i].c!=q1[i+1].c)
q[++nn]=q1[i],q[nn].w=cnt,cnt=0;
}
cdq(1,nn);
for (int i=1;i<=nn;i++) t[q[i].ans+q[i].w-1]+=q[i].w;
for (int i=0;i<n;i++) printf("%d\n",t[i]);
return 0;
}
|