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，先递归。

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

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

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

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