题目地址：洛谷：【P3810】【模板】三维偏序（陌上花开） – 洛谷、BZOJ：Problem 3262. — 陌上花开

题目描述

有n朵花,每朵花有三个属性:花形(s)、颜色(c)、气味(m),用三个整数表示。
现在要对每朵花评级,一朵花的级别是它拥有的美丽能超过的花的数量。
定义一朵花A比另一朵花B要美丽,当且仅Sa>=Sb,Ca>=Cb,Ma>=Mb。
显然,两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。

题意简述

有$n$个三元组，定义三元组的大于关系为$(a_1, b_1, c_1) \geq (a_2, b_2, c_2) \Leftrightarrow a_1 \geq a_2, b_1 \geq b_2, c1 \geq c_2$。对于每个三元组，我们可以求出在这个三元组集合中除它自己以外，它大于等于的三元组数量，求答案为每种可能的取值的三元组数量。

输入输出格式

输入格式：
第一行为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：

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

输出样例#1：

3
1
3
0
1
0
1
0
0
1

题解

参考资料：bzoj 3263 陌上花开（cdq分治，BIT） – hahalidaxin – 博客园
我们先将所有的三元组三关键字排好序，显然，比每个三元组三个属性都不大于的三元组应该在这个三元组的前面，至少，在这次排序中，我们确保了第一个属性是有序的。
接下来我们要使用cdq分治和数据结构解决这个问题。我们考虑一个类似归并排序的过程，对于一个需要计算的区间$[l, r]$，先递归地处理$[l, mid]$和$[mid + 1, r]$内部的答案，然后考虑跨区间的贡献，由于最开始的排序，此时的右半区间中的元素的第一属性一定不小于左半边区间中的元素，而由于我们之前的处理，各半边区间中的元素的第二属性是有序的，因此我们使用树状数组维护当前左半边区间内的每个第三属性值有多少元素对应，然后遍历到右半区间的元素的时候，利用前缀和统计贡献即可。这个过程有点类似于归并排序合并区间的操作。
这就是为什么大多数这个题的题解中都提到了一句话：

第一维排序，第二维cdq分治，第三维树状数组

总的来说，cdq分治是一种类似归并排序的方法，先分别处理左右半区间的内部答案并进行一定的排序，然后利用排序的性质来合并区间，统计跨区间贡献。
总复杂度$O(n \log^2 n)$。

代码

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 200005;

int n, k;

int tr[MAXN];

inline int lowbit(int x) {
    return x & -x;
}

inline void add(int x, int v) {
    for(int i = x; i <= k; i += lowbit(i)) {
        tr[i] += v;
    }
}

inline int query(int x) {
    int res = 0;
    for(int i = x; i; i -= lowbit(i)) {
        res += tr[i];
    }
    return res;
}

struct Node {
    int a, b, c, cnt, ans;
    Node() {}
    Node(Node &x, int _cnt) {
        *this = x; cnt = _cnt;
    }
    inline bool operator<(const Node &rhs) const {
        if(a == rhs.a && b == rhs.b) return c < rhs.c;
        else if(a == rhs.a) return b < rhs.b;
        else return a < rhs.a;
    }
    inline bool operator!=(const Node &rhs) const {
        return a != rhs.a || b != rhs.b || c != rhs.c;
    }
} a[MAXN], b[MAXN], t[MAXN];

inline bool cmp(Node a, Node b) {
    return a.b == b.b ? a.c < b.c : a.b < b.b;
}

void cdqdivide(int l, int r) {
    if(l == r) return;
    int mid = (l + r) >> 1;
    cdqdivide(l, mid); cdqdivide(mid + 1, r);
    int l1 = l, l2 = mid + 1;
    while(l2 <= r) {
        while(l1 <= mid && b[l1].b <= b[l2].b) {
            add(b[l1].c, b[l1].cnt); l1++;
        }
        b[l2].ans += query(b[l2].c); l2++;
    }
    for(int i = l; i < l1; i++) {
        add(b[i].c, -b[i].cnt);
    }
    l1 = l; l2 = mid + 1; int p = l;
    while(l1 <= mid && l2 <= r) {
        if(cmp(b[l1], b[l2])) t[p++] = b[l1++];
        else t[p++] = b[l2++];
    }
    while(l1 <= mid) t[p++] = b[l1++];
    while(l2 <= r) t[p++] = b[l2++];
    for(int i = l; i <= r; i++) b[i] = t[i];
}

int ans[MAXN];

int main() {
    n = readint(); k = readint();
    for(int i = 1; i <= n; i++) {
        a[i].a = readint(); a[i].b = readint(); a[i].c = readint();
    }
    std::sort(a + 1, a + n + 1);
    int cnt = 0, tot = 0;
    for(int i = 1; i <= n; i++) {
        cnt++;
        if(a[i] != a[i + 1]) {
            b[++tot] = Node(a[i], cnt); cnt = 0;
        }
    }
    cdqdivide(1, tot);
    for(int i = 1; i <= tot; i++) {
        ans[b[i].ans + b[i].cnt - 1] += b[i].cnt;
    }
    for(int i = 0; i < n; i++) {
        printf("%d\n", ans[i]);
    }
    return 0;
}