题目描述 有$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].a且S[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); }
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 ; }
