「BZOJ 3262」陌上花开 - CDQ

定义一个序列，序列中每个元素都是一个三元组 。 若 ，则称 比 优。 定义 的等级为有多少 满足 比 更优。

求每个等级的元素数量。

链接

BZOJ 3262

题解

经典的三维偏序问题，使用 CDQ 分治解决。

首先，将第一维排序，进行 CDQ 分治。分治时保证前一半元素的 始终小于等于后一半，并且两半分别按照 升序。

分治完两半之后，将两半按照 归并，并同时对 维护树状数组，动态查询有多少点的 小于等于当前点。树状数组保证了 的大小关系，归并保证了 的大小关系，排序保证了 的大小关系，CDQ 保证了对一个元素有贡献的所有元素都被考虑的到。

每一次分治完成后需要清空树状数组。

注意可能有多个重复的元素，此时只需记录一个元素出现的次数即可。一个元素会对它本身的答案有贡献，在分治到最后一层时对其赋值即可。

代码

#include <cstdio>
#include <algorithm>

const int MAXN = 100000;
const int MAXK = 200000;

struct Triple {
    int a, b, c, cnt, ans;
} a[MAXN], A[MAXN];

bool operator<(const Triple &a, const Triple &b) {
    return a.a < b.a || (a.a == b.a && a.b < b.b) || (a.a == b.a && a.b == b.b && a.c < b.c);
}

int n, k;

struct BinaryIndexedTree {
    int a[MAXK];

    static int lowbit(const int x) { return x & -x; }

    int query(const int x) {
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)) ans += a[i - 1];
        return ans;
    }

    void update(const int x, const int delta) {
        for (int i = x; i <= k; i += lowbit(i)) a[i - 1] += delta;
    }

    void clean(const int x) {
        for (int i = x; i <= k; i += lowbit(i)) {
            if (a[i - 1]) a[i - 1] = 0;
            else break;
        }
    }
} bit;

inline void cdq(Triple *l, Triple *r) {
    if (l == r) {
        l->ans += l->cnt - 1;
        return;
    }

    Triple *mid = l + (r - l) / 2;

    cdq(l, mid);
    cdq(mid + 1, r);

    static Triple tmp[MAXN];
    for (Triple *p = tmp, *p1 = l, *p2 = mid + 1; p <= tmp + (r - l); p++) {
        if ((p1->b <= p2->b && p1 <= mid) || p2 > r) {
            *p = *p1++;
            bit.update(p->c, p->cnt);
        } else {
            *p = *p2++;
            p->ans += bit.query(p->c);
        }
    }

    for (Triple *p = tmp, *q = l; q <= r; p++, q++) {
        bit.clean(p->c);
        *q = *p;
    }

    /*
    printf("cdq(%ld, %ld): ", l - A + 1, r - A + 1);
    for (Triple *p = l; p <= r; p++) {
        printf("(%d, %d, %d)%s", p->a, p->b, p->c, p == r ? "\n" : ", ");
    }
    */
}

template <typename T>
inline void read(T &x) {
    x = 0;
    register char ch;
    while (ch = getchar(), !(ch >= '0' && ch <= '9'));
    do x = x * 10 + (ch - '0'); while (ch = getchar(), (ch >= '0' && ch <= '9'));
}

template <typename T>
inline void write(T &x) {
    static char s[20];
    int cnt = 0;
    do s[cnt++] = x % 10; while (x /= 10);
    while (cnt--) putchar(s[cnt] + '0');
    putchar('\n');
}

int main() {
    read(n), read(k);
    for (int i = 0; i < n; i++) read(a[i].a), read(a[i].b), read(a[i].c), a[i].cnt = 1;
    // scanf("%d %d", &n, &k);
    // for (int i = 0; i < n; i++) scanf("%d %d %d", &a[i].a, &a[i].b, &a[i].c), a[i].cnt = 1;

    std::sort(a, a + n);

    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (i == 0 || !(a[i].a == a[i - 1].a && a[i].b == a[i - 1].b && a[i].c == a[i - 1].c)) A[cnt++] = a[i];
        else A[cnt - 1].cnt++;
    }

    cdq(A, A + cnt - 1);

    static int ans[MAXN];
    for (int i = 0; i < cnt; i++) ans[A[i].ans] += A[i].cnt;

    for (int i = 0; i < n; i++) write(ans[i]);
    // for (int i = 0; i < n; i++) printf("%d\n", ans[i]);

    return 0;
}