题目链接：LOJ 112

有 $n$ 个元素，第 $i$ 个元素有 $a_i$、$b_i$、$c_i$ 三个属性，设 $f(i)$ 表示满足 $a_j \le a_i$ 且 $b_j \le b_i$ 且 $c_j \le c_i$ 的 $j$ 的数量。

对于 $d \in [0, n)$，求 $f(i) = d$ 的 $i$ 的数量。

数据范围：$1 \le n \le 10 ^ 5$，$1 \le a_i, b_i, c_i \le 2 \times 10 ^ 5$。

Solution

如果有重复的处理起来就比较麻烦，于是我们先去重，记录每个属性有多少朵花。

这题就是一个裸的 $\text{CDQ}$ 分治。我们对第一维 $S_i$ 排序，这样可以忽略第一维的影响；对第二份进行分治，合并时我们用树状数组记录每个 $M_i$ 出现的次数，和统计逆序对类似的方法计算左区间对右区间的贡献。

时间复杂度：$\mathcal O(n\log^2 n)$。

Code

#include <cstdio>
#include <algorithm>

const int N = 2e5 + 5;

int n, k, f[N];

struct Data {
    int x, y, z, idx, cnt, ans;
    bool operator!=(const Data &b) const {
        return x != b.x || y != b.y || z != b.z;
    }
} a[N], t[N];

struct BIT {
    int b[N];
    void add(int x, int v) {
        for (; x <= k; x += x & -x) b[x] += v;
    }
    int query(int x) {
        int ans = 0;
        for (; x; x ^= x & -x) ans += b[x];
        return ans;
    }
} bit;

void CDQ(int l, int r) {
    if (l == r) return;
    int m = (l + r) >> 1;
    CDQ(l, m), CDQ(m + 1, r);
    std::merge(a + l, a + m + 1, a + m + 1, a + r + 1, t + l, [](Data a, Data b) {
        return a.y < b.y;
    });
    std::copy(t + l, t + r + 1, a + l);
    for (int i = l; i <= r; i++) {
        if (a[i].idx <= m) {
            bit.add(a[i].z, a[i].cnt);
        } else {
            a[i].ans += bit.query(a[i].z);
        }
    }
    for (int i = l; i <= r; i++) {
        if (a[i].idx <= m) bit.add(a[i].z, -a[i].cnt);
    }
}
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].z);
    }
    std::sort(a + 1, a + n + 1, [](Data a, Data b) {
        return a.x == b.x ? a.y == b.y ? a.z < b.z : a.y < b.y : a.x < b.x;
    });
    int tot = 0;
    for (int i = 1; i <= n; i++) {
        if (!tot || a[i] != a[i - 1]) a[++tot] = a[i], a[tot].idx = tot;
        a[tot].cnt++;
    }
    CDQ(1, tot);
    for (int i = 1; i <= tot; i++) f[a[i].ans + a[i].cnt - 1] += a[i].cnt;
    for (int i = 0; i < n; i++) printf("%d\n", f[i]);
    return 0;
}