Description
有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽，当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb。显然，两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。
第一行为N,K (1 <= N <= 100,000, 1 <= K <= 200,000 ), 分别表示花的数量和最大属性值。
以下N行，每行三个整数si, ci, mi (1 <= si, ci, mi <= K)，表示第i朵花的属性
Output
包含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
|
Sample Output
1
2
3
4
5
6
7
8
9
10
| 3
1
3
0
1
0
1
0
0
1
|
HINT
1 <= N <= 100,000, 1 <= K <= 200,000
Solution
一些题外话：
还记得当初就是因为这道题才开的权限QAQ，可惜当时不会做这题。。。现在刷起来好有岁月感。。。
我们对s排序，建立K颗平衡树，平衡树T_i保存c为1的花到c为i的花的m的值。可以发现我们其实是在维护一个前缀和。于是用树状数组维护这个前缀和就好了。排序NlogN，树状数组LogK，平衡树logN，一共N朵花，于是时间复杂度为NlogNlogK，空间复杂度为NlogK。
然后巨慢。。。（总算跑过了QAQ，第一次RE，数组开小。。。）有一种很快的方法用的是CDQ分治。
Code
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
| #include <cstdio>
#include <algorithm>
using namespace std;
int getint() {
int r = 0, k = 1; char c = getchar();
for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
return r * k;
}
const int maxn = 100005;
struct Flower_type {
int a, b, c;
} F[maxn];
int N, K;
inline bool cmp (Flower_type a, Flower_type b) { return a.a < b.a; }
int rd[maxn * 60], fa[maxn * 60], tot, siz[maxn * 60], c[maxn * 60][2], val[maxn * 60];
struct Treap {
int root;
inline int gr() { return (rand() << 15) ^ rand(); }
void pu(int x) {
siz[x] = 1;
if (c[x][0]) siz[x] += siz[c[x][0]];
if (c[x][1]) siz[x] += siz[c[x][1]];
}
void rotate(int x) {
int y = fa[x], z = fa[y], a = (c[y][1] == x), b = a ^ 1;
if (z) c[z][c[z][1]==y] = x;
fa[x] = z; fa[y] = x; fa[c[x][b]] = y; fa[0] = 0;
c[y][a] = c[x][b]; c[x][b] = y;
pu(y); pu(x);
}
void insert(int &x, int key, int father) {
if (!x) {
x = ++tot;
fa[tot] = father;
val[tot] = key;
rd[tot] = gr();
siz[tot] = 1;
while (fa[tot] && rd[fa[tot]] < rd[tot]) rotate(tot);
if (!fa[tot]) root = tot;
return;
}
++siz[x];
if (key < val[x]) insert(c[x][0], key, x);
else insert(c[x][1], key, x);
}
int ask(int x, int key) {
if (!x) return 0;
if (val[x] <= key) return siz[c[x][0]] + 1 + ask(c[x][1], key);
else return ask(c[x][0], key);
}
};
struct BIT {
Treap T[maxn * 2];
inline int lowbit(int x) { return x & (-x); }
void INSERT(int pos) {
for (int i = F[pos].b; i <= K; i += lowbit(i)) T[i].insert(T[i].root, F[pos].c, 0);
}
int ASK(int pos) {
int ret = 0;
for (int i = F[pos].b; i; i -= lowbit(i)) ret += T[i].ask(T[i].root, F[pos].c);
return ret;
}
} B;
int LV[maxn], Ans[maxn];
int main() {
srand(20000926);
N = getint(); K = getint();
for (int i = 1; i <= N; ++i) {
F[i].a = getint(); F[i].b = getint(); F[i].c = getint();
}
F[N+1].a = F[N+1].b = F[N+1].c = -1;
sort(F + 1, F + N + 1, cmp);
for (int i = 1; i <= N;) {
int ed = i; B.INSERT(i);
while (F[ed+1].a == F[ed].a) {
++ed;
B.INSERT(ed);
}
for (; i <= ed; ++i) LV[i] = B.ASK(i);
}
for (int i = 1; i <= N; ++i) ++Ans[LV[i]];
for (int i = 1; i <= N; ++i) printf("%d\n", Ans[i]);
return 0;
}
|