题目描述

有$n$朵花,每朵花有三个属性:花形($S$)、颜色($C$)、气味($M$),用三个整数表示。

现在要对每朵花评级,一朵花的级别是它拥有的美丽能超过的花的数量。

定义一朵花A比另一朵花B要美丽,当且仅$S_a>=S_b,C_a>=C_b,M_a>=M_b$。

显然,两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。

输入格式

第一行为$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\dots N-1$的每级花的数量。

题解

cdq分治模板题

我对cdq分治的理解是这样的:

有的时候 一些乱序的东西 我们要计算它们两两之间的贡献(或者转移贡献,比如dp),把它们按照一定的(多维)顺序计算或转移才会比较方便;这时候就可以用cdq分治一维一维地进行处理

比如 此题的思路是这样的:

为了方便 我们把$S$称为$a$,$C$称为$b$,$M$称为$c$。

我们先来看看这道简化版的题:

有两个花的集合 一个是$S$一个是$T$。 求:对于每个$T$中的元素$j$有多少个$S$中的元素$i$满足S[i].a<=T[j].aS[i].b<=T[j].b

这个问题很好解决 我们分别把$S$和$T$中元素按照$a$排序 然后维护双指针和树状数组 每次枚举到$T$中的一个元素$j$时 就把$S$中所有现在满足了S[i].a<=T[j].a的花放进去 然后再统计$j$的答案

1
2
3
4
5
6
7
8
9
10
void solve(int n, int m) {
int i, j;
for (i = 1, j = 1; j <= m; j++) {
while (i <= n && S[i].a <= T[j].a) {
update(S[i].b, 1); //放入树状数组
i++;
}
T[j].ans = getsum(T[j].b);
}
}

然后我们把问题扩展到三维

先把所有花按照$a$排序,然后开始进行分治:

首先要理解一点,分治时solve(l,r)实际上就是在计算[l,mid][mid+1,r]两组元素两两匹配的贡献

我们看看怎么来solve(l,r)

第一步是先递归解决solve(l,mid)solve(mid+1,r)

1
2
3
if (l == r) return;
int mid = (l + r) >> 1;
solve(l, mid); solve(mid+1, r);

这个其实是因题而异的 这题因为对[l,r]的后续排序(下面这个排序)可能会影响到这个初始时以$a$为第一关键字的顺序 所以要先把两个子区间计算完

然后我们分别把[l,mid][mid+1,r]以$b$为第一关键字排序

1
sort(p + l, p + mid + 1, cmp2); sort(p + mid + 1, p + r + 1, cmp2);

注意 这样排序之后 虽然[l,mid]区间内可能不满足$a$单调不降了 但是[l,mid]区间内任意一个$a$仍然是小于等于[mid+1,r]区间内任意一个$a$的(划重点!!!) 所以我们用右半边匹配左半边时是不用考虑$a$的问题的

现在两边都已经按照$b$排序了 且右半边的$a$一定大于等于左半边任意一个$a$所以$a$这一维已经相当于没用了 直接扔了 然后这是不是就变成了上面的”简化版问题”了呢?即由[mid+1,r]中的元素构成的集合$T$去匹配[l,mid]构成的集合$S$

那么我们就直接用上面的方法进行匹配

1
2
3
4
5
6
7
8
int i, j;
for (i = l, j = mid + 1; j <= r; j++) {
while (i <= mid && p[j].b >= p[i].b) {
update(p[i].c, 1);
i++;
}
p[j].ans += getsum(p[j].c); //注意这里是加算,j的答案不止统计一次
}

solve完之后记得清空树状数组

1
2
3
for (j = l; j < i; j++) {
update(p[j].c, -1);
}

这就是solve的全过程了 不知道我写的易不易懂QAQ

为了方便理解,我们透过现象看看这个事情的本质(不是)

比如说$n=8$我们看看按$a$排序后第8位被统计了几次贡献:

首先 solve(7,8)的时候,计算了[7,7]对8的贡献
solve(5,8)时,计算了[5,6]的贡献
solve(1,8)时,计算了[1,4]的贡献

所以 实际上 所有$a$值小于第8位的花都有与8尝试匹配过 随便换个数也是这样

所以这个算法是正确的

再来看看时间复杂度$T(n)=2T(n/2)+n\log n$得到复杂度是$O(n\log^2 n)$的

然后这题还有一个小细节:会出现一模一样的元素

由于两个一样的元素$x,y$,$x$满足$a_x\le a_y,~b_x\le b_y, ~c_x\le c_y$,反过来也满足,所以没法直接用分治算

我们可以把相同的元素全部合并到一起 像离散化一样 然后记录一下这种元素共有多少个 记为$cnt_i$

最后统计答案时 某种花的评级应该是(小于它的花的总数量+这种花的数量-1) 因为相同的花会两两相互产生贡献。。。

代码

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
#include <bits/stdc++.h>
using namespace std;

template<typename T>
inline void read(T &num) {
T x = 0, f = 1; char ch = getchar();
for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1;
for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0');
num = x * f;
}

int n, m, ak, ans[100005];

struct node{
int a, b, c, cnt, ans;
} tmp[100005], p[100005];

inline bool cmp1(node x, node y) {
if (x.a != y.a) return x.a < y.a;
else if (x.b != y.b) return x.b < y.b;
else return x.c < y.c;
}

inline bool cmp2(node x, node y) {
if (x.b != y.b) return x.b < y.b;
else return x.c < y.c;
}

//树状数组

int tr[200005];

inline void update(int x, int v) {
for (; x <= 200000; x += x & -x) {
tr[x] += v;
}
}

inline int getsum(int x) {
int ret = 0;
for (; x; x -= x & -x) {
ret += tr[x];
}
return ret;
}

void solve(int l, int r) {
if (l == r) return;
int mid = (l + r) >> 1;
solve(l, mid); solve(mid+1, r);
sort(p + l, p + mid + 1, cmp2); sort(p + mid + 1, p + r + 1, cmp2);
int i, j;
for (i = l, j = mid + 1; j <= r; j++) {
while (i <= mid && p[j].b >= p[i].b) {
update(p[i].c, p[i].cnt);
i++;
}
p[j].ans += getsum(p[j].c);
}
for (j = l; j < i; j++) {
update(p[j].c, -p[j].cnt);
}
}

int main() {
read(n); read(ak);
for (int i = 1; i <= n; i++) {
read(tmp[i].a), read(tmp[i].b), read(tmp[i].c);
}
sort(tmp + 1, tmp + n + 1, cmp1);

int now = 1;
for (int i = 2; i <= n; i++) { //去重
if (tmp[i].a == tmp[i-1].a && tmp[i].b == tmp[i-1].b && tmp[i].c == tmp[i-1].c) {
now++;
} else {
p[++m].a = tmp[i-1].a; p[m].b = tmp[i-1].b; p[m].c = tmp[i-1].c;
p[m].cnt = now; p[m].ans = 0; now = 1;
}
}
p[++m].a = tmp[n].a; p[m].b = tmp[n].b; p[m].c = tmp[n].c;
p[m].cnt = now; p[m].ans = 0; now = 1;

solve(1, m);
for (int i = 1; i <= m; i++) {
ans[p[i].ans + p[i].cnt - 1] += p[i].cnt;
}
for (int i = 0; i < n; i++) {
printf("%d\n", ans[i]);
}
return 0;
}

评论