NekoMio's Blog

美しいものが起こることを常に信じている

  1. 1. 题目描述
  2. 2. 输入格式
  3. 3. 输出格式
  4. 4. 样例输入
  5. 5. 样例输出
  6. 6. 提示
  • 题解
  • 题目描述

    有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 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

    样例输出

    3
    1
    3
    0
    1
    0
    1
    0
    0
    1

    提示

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

    题解

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

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

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

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

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

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

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

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

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

    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
    #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);
    }

    本文作者 : NekoMio
    知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
    本文链接 : https://www.nekomio.com/2017/10/25/116/

    本文最后更新于 天前,文中所描述的信息可能已发生改变