831 字
4 分钟
BZOJ 3262 陌上花开 CDQ
题目描述
有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朵花的属性
输出格式
包含N行,分别表示评级为0…N-1的每级花的数量。
样例输入
10 33 3 32 3 32 3 13 1 13 1 21 3 11 1 21 2 21 3 21 2 1
样例输出
3130101001
提示
1 <= N <= 100,000, 1 <= K <= 200,000
题解
三维偏序
将一个维度作为时间。
比如我令 颜色(c) 为时间维。
那么第一步将除时间(颜色)以外的一个维度排序,
比如说我这里将 花形(s) 排序
那么我们要保证这一维(花形) 时刻有序。
然后我们分治时间(颜色);
我选择的方法是暴力sort
, 先递归。
那么在分治后左边的花型一定是小于右边的。
所以只要将左右分别按时间排序, 对于每一个右边的值, 将左边时间比他小的更新到树状数组中。 然后查询第三维小于他的个数就可以更新答案了。
一些具体的细节可以看代码实现
#include <cstdio>#include <algorithm>#include <cstring>using namespace std;const int N = 100005;const int M = 200005;struct data{ int s, c, m, pos, num, ans; bool operator < (const data &a) const { if (s == a.s && c == a.c) return m < a.m; if (s == a.s) return c < a.c; return s < a.s; }}a[N], b[N];const bool cmp(const data &a, const data &b){ if (a.c == b.c) a.m < b.m; return a.c < b.c;}int Sum[M], cnt, Color[M], C;#define lowbit(_) ((_) & (-_))void add(int x, int c){ for (int i = x; i <= M; i += lowbit(i)) { if (Color[i] != C) Sum[i] = 0; Color[i] = C; Sum[i] += c; }}int Query(int x){ int ans = 0; for (int i = x; i > 0; i -= lowbit(i)) { if (Color[i] == C) ans += Sum[i]; } return ans;}void CDQ(int l, int r){ if (l == r) return; int mid = l + r >> 1; CDQ(l, mid), CDQ(mid + 1, r); sort(b + l, b + mid + 1, cmp); sort(b + mid + 1, b + r + 1, cmp); C++; for (int j = mid + 1, i = l; j <= r; j++) { for (; b[i].c <= b[j].c && i <= mid; i++) add(b[i].m, b[i].num); b[j].ans += Query(b[j].m); }}int main(){ int n, k; scanf ("%d%d", &n, &k); for (int i = 1; i <= n; i++){ scanf ("%d%d%d", &a[i].s, &a[i].c, &a[i].m); a[i].pos = i; } sort(a + 1, a + n + 1); for (int i = 1; i <= n; i++) { if (a[i].c == a[i - 1].c && a[i].s == a[i - 1].s && a[i].m == a[i - 1].m) b[cnt].num++; else b[++cnt] = a[i], b[cnt].num = 1; } // for (int i = 1; i <= cnt; i++) printf ("%d%c", b[i].pos, " \n"[i == cnt]); CDQ(1, cnt); // for (int i = 1; i <= cnt; i++) printf ("%d%c", b[i].ans, " \n"[i == cnt]); // while(1); static int Ans[N]; for (int i = 1; i <= cnt; i++) Ans[b[i].ans + b[i].num - 1] += b[i].num; for (int i = 0; i < n; i++) printf ("%d\n", Ans[i]); // while (1);}
BZOJ 3262 陌上花开 CDQ
https://www.nekomio.com/posts/116/