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
| #include <iostream>
#include <cstdio>
#define maxn 100010
#define maxm 200010
#define lowbit(i) ((i) & (-i))
#define cQ const Query
using namespace std;
int n, m;
int Bit[maxm];
void add(int i, int v) { while (i <= m) Bit[i] += v, i += lowbit(i); }
int get_sum(int i) {
int s = 0;
while (i) s += Bit[i], i -= lowbit(i);
return s;
}
struct Query {
int x, y, z, v, ans;
friend bool operator < (cQ &u, cQ &v) { return u.y < v.y; }
} Q[maxn], tmp[maxn]; int cnt;
inline bool cmp(cQ &u, cQ &v) {
if (u.x == v.x && u.y == v.y) return u.z < v.z;
if (u.x == v.x) return u.y < v.y;
return u.x < v.x;
}
inline bool pd(cQ &u, cQ &v) {
return u.x == v.x && u.y == v.y && u.z == v.z;
}
void cdq(int l, int r) {
if (l == r) return ; int m = l + r >> 1, j = l - 1;
cdq(l, m); cdq(m + 1, r);
for (int i = m + 1; i <= r; ++i) {
while (j < m && Q[j + 1].y <= Q[i].y) ++j, add(Q[j].z, Q[j].v);
Q[i].ans += get_sum(Q[i].z);
}
for (int i = l; i <= j; ++i) add(Q[i].z, -Q[i].v);
inplace_merge(Q + l, Q + m + 1, Q + r + 1);
}
int ans[maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> tmp[i].x >> tmp[i].y >> tmp[i].z;
sort(tmp + 1, tmp + n + 1, cmp);
for (int i = 1, w = 1; i <= n; ++i)
if (!pd(tmp[i], tmp[i + 1]))
Q[++cnt] = tmp[i], Q[cnt].v = w, w = 1;
else ++w;
cdq(1, cnt);
for (int i = 1; i <= cnt; ++i) ans[Q[i].ans + Q[i].v - 1] += Q[i].v;
for (int i = 0; i < n; ++i) cout << ans[i] << "\n";
return 0;
}
|