「BZOJ-3262」陌上花开-CDQ分治

有$n$朵花,每朵花有三个属性:花形$(s)$、颜色$(c)$、气味$(m)$,又三个整数表示。现要对每朵花评级,一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花$A$比另一朵花$B$要美丽,当且仅当$S_a$>=$S_b$,$C_a$>=$C_b$,$M_a$>=$M_b$。显然,两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。

链接

bzoj-3262

输入

第一行为$N,K$ $(1 <= N <= 100,000, 1 <= K <= 200,000 ),$ 分别表示花的数量和最大属性值。
以下N行,每行三个整数$s_i, c_i, m_i (1 <= s_i, c_i, m_i <= K)$,表示第i朵花的属性

输出

包含N行,分别表示评级为$0…N-1$的每级花的数量。

样例

输入

1
2
3
4
5
6
7
8
9
10
11
10 3
3 3 3
2 3 3
2 3 1
3 1 1
3 1 2
1 3 1
1 1 2
1 2 2
1 3 2
1 2 1

输出

1
2
3
4
5
6
7
8
9
10
3
1
3
0
1
0
1
0
0
1

$1 <= N <= 100,000, 1 <= K <= 200,000$

题解

此题可写树套树,然而CDQ分治显然更好写,分治一维,归并排序一维,树状数组处理一维即可

代码

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#define inf 0x7fffffff
#define ll long long
using namespace std;
inline void R(int &v) {
static char ch;
v = 0;
bool p = 0;
do {
ch = getchar();
if (ch == '-')
p = 1;
} while ( !isdigit(ch) );
while ( isdigit(ch) ) {
v = ( v << 1 ) + ( v << 3 ) + ( ch ^ '0' );
ch = getchar();
}
if (p)
v = -v;
}
int n, m, t[200005], ans[100005], N;
struct data {
int a, b, c, s, ans;
} a[100005], p[100005], temp[100005];
inline bool cmp(data a, data b) {
if (a.a == b.a && a.b == b.b) return a.c < b.c;
if (a.a == b.a) return a.b < b.b;
return a.a < b.a;
}
inline bool operator < (data a, data b) {
if (a.b == b.b) return a.c < b.c;
return a.b < b.b;
}
inline int lowbit(int x) {
return x & ( -x );
}
inline void update(int x, int num) {
for ( int i = x; i <= m; i += lowbit(i) )
t[i] += num;
}
inline int ask(int x) {
int tmp = 0;
for ( int i = x; i; i -= lowbit(i) )
tmp += t[i];
return tmp;
}
void solve(int l, int r) {
if (l >= r) return;
int mid = ( l + r ) >> 1;
solve(l, mid);
solve(mid + 1, r);
int mid1 = ( l + mid ) >> 1;
int i = l, j = mid1 + 1, k = 0;
for (; i <= mid1 || j <= mid; ) {
if ( i <= mid1 && ( ( j > mid ) || ( p[i] < p[j] ) ) ) temp[++k] = p[i++];
else temp[++k] = p[j++];
}
j = l;
for (int i = 1; i <= k; ++i) {
p[j++] = temp[i];
}
mid1 = ( mid + 1 + r ) >> 1;
i = mid + 1, j = mid1 + 1, k = 0;
for (; i <= mid1 || j <= r; ) {
if ( i <= mid1 && ( ( j > r ) || ( p[i] < p[j] ) ) ) temp[++k] = p[i++];
else temp[++k] = p[j++];
}
j = mid + 1;
for (int i = 1; i <= k; ++i) {
p[j++] = temp[i];
}
i = l, j = mid + 1;
while (j <= r) {
while (i <= mid && p[i].b <= p[j].b) {
update(p[i].c, p[i].s);
i++;
}
p[j].ans += ask(p[j].c);
j++;
}
for (int j = l; j < i; j++) update(p[j].c, -p[j].s);
}
int main() {
R(N);
R(m);
for (int i = 1; i <= N; i++)
R(a[i].a), R(a[i].b), R(a[i].c);
sort(a + 1, a + N + 1, cmp);
int cnt = 0;
for (int i = 1; i <= N; i++) {
cnt++;
if (a[i].a ^ a[i + 1].a || a[i].b ^ a[i + 1].b || a[i].c ^ a[i + 1].c) {
p[++n] = a[i];
p[n].s = cnt;
cnt = 0;
}
}
solve(1, n);
for (int i = 1; i <= n; i++)
ans[p[i].ans + p[i].s - 1] += p[i].s;
for (int i = 0; i < N; i++)
cout << ans[i] << '\n';
return 0;
}
文章目录
  1. 1. 链接
  2. 2. 输入
  3. 3. 输出
  4. 4. 样例
    1. 4.1. 输入
    2. 4.2. 输出
  5. 5. 题解
  6. 6. 代码