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的每级花的数量。

样例输入#

样例输出#

提示#

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

题解#

三维偏序
将一个维度作为时间。

比如我令 颜色(c) 为时间维。

那么第一步将除时间(颜色)以外的一个维度排序，
比如说我这里将 花形(s) 排序

那么我们要保证这一维(花形) 时刻有序。

然后我们分治时间(颜色);

我选择的方法是暴力sort，先递归。

那么在分治后左边的花型一定是小于右边的。

所以只要将左右分别按时间排序，对于每一个右边的值，将左边时间比他小的更新到树状数组中。然后查询第三维小于他的个数就可以更新答案了。

一些具体的细节可以看代码实现

1
#include <cstdio>
2
#include <algorithm>
3
#include <cstring>
4
using namespace std;
5
const int N = 100005;
6
const int M = 200005;
7
struct data
8
{
9
    int s, c, m, pos, num, ans;
10
    bool operator < (const data &a) const
11
    {
12
        if (s == a.s && c == a.c) return m < a.m;
13
        if (s == a.s) return c < a.c;
14
        return s < a.s;
15
    }
16
}a[N], b[N];
17
const bool cmp(const data &a, const data &b)
18
{
19
    if (a.c == b.c) a.m < b.m;
20
    return a.c < b.c;
21
}
22
int Sum[M], cnt, Color[M], C;
23
#define lowbit(_) ((_) & (-_))
24
void add(int x, int c)
25
{
26
    for (int i = x; i <= M; i += lowbit(i))
27
    {
28
        if (Color[i] != C) Sum[i] = 0;
29
        Color[i] = C;
30
        Sum[i] += c;
31
    }
32
}
33
int Query(int x)
34
{
35
    int ans = 0;
36
    for (int i = x; i > 0; i -= lowbit(i))
37
    {
38
        if (Color[i] == C)
39
            ans += Sum[i];
40
    }
41
    return ans;
42
}
43
void CDQ(int l, int r)
44
{
45
    if (l == r) return;
46
    int mid = l + r >> 1;
47
    CDQ(l, mid), CDQ(mid + 1, r);
48
    sort(b + l, b + mid + 1, cmp);
49
    sort(b + mid + 1, b + r + 1, cmp);
50
    C++;
51
    for (int j = mid + 1, i = l; j <= r; j++)
52
    {
53
        for (; b[i].c <= b[j].c && i <= mid; i++)
54
            add(b[i].m, b[i].num);
55
        b[j].ans += Query(b[j].m);
56
    }
57
}
58
int main()
59
{
60
    int n, k;
61
    scanf ("%d%d", &n, &k);
62
    for (int i = 1; i <= n; i++){
63
        scanf ("%d%d%d", &a[i].s, &a[i].c, &a[i].m);
64
        a[i].pos = i;
65
    }
66
    sort(a + 1, a + n + 1);
67
    for (int i = 1; i <= n; i++)
68
    {
69
        if (a[i].c == a[i - 1].c && a[i].s == a[i - 1].s && a[i].m == a[i - 1].m)
70
            b[cnt].num++;
71
        else
72
            b[++cnt] = a[i], b[cnt].num = 1;
73
    }
74
    // for (int i = 1; i <= cnt; i++) printf ("%d%c", b[i].pos, " \n"[i == cnt]);
75
    CDQ(1, cnt);
76
    // for (int i = 1; i <= cnt; i++) printf ("%d%c", b[i].ans, " \n"[i == cnt]);
77
    // while(1);
78
    static int Ans[N];
79
    for (int i = 1; i <= cnt; i++) Ans[b[i].ans + b[i].num - 1] += b[i].num;
80
    for (int i = 0; i < n; i++) printf ("%d\n", Ans[i]);
81
    // while (1);
82
}