原理

cdq 分治： 对于一个区间$[l,r]$进行操作时，先对$[l,mid]$和$[mid+1,r]$进行操作，然后统计$[l,mid]$对$[mid+1,r]$的影响，最终得到结果，这样的过程就是 cdq 分治。

偏序问题

考虑对于$\forall i$，如何计算$a_i\geq a_j,b_i\geq b_j,c_i\geq c_j$的$j$的个数。

可以渐进地思考这个问题：

逆序对

直接搞个权值树状数组作为一个桶，然后从右到左扫一遍；或者归并排序统计答案即可。当然也可以用与解决顺序对问题。

二维偏序

如果是二维，考虑对一维的每个数构造数对$(i,a_i)$，显然对于一个顺序对$(a_i,a_j)$有$i<j,a_i<a_j$，么按$a$排序以后，就转化为了一维顺序对问题。

这样就得出了一个很重要的结论：在偏序问题中，只要有一位有序，那么就可以直接忽略这一维。这也为降维提供了可能性。

回到三维偏序问题，假设$a$有序，那么就可以直接忽略$a$的影响了；再考虑对$b$进行类似于归并排序的处理，同时使用 cdq 分治，对$c$构造一个权值树状数组，每次只需要统计$c_j\leq c_i$的个数即可。

另外，还有两个坑点：

树状数组在每次归并排序完成之后必须清空，否则会不停加下去；
$a,b,c$全部相等的情况需要特判处理。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
const int MAXK = 2e5 + 10;
struct _node {
    int a, b, c, ans;
} node[MAXN];
int cnt[MAXN];

bool cmp1(const _node &lhs, const _node &rhs) {
    if (lhs.a != rhs.a)
        return lhs.a < rhs.a;
    if (lhs.b != rhs.b)
        return lhs.b < rhs.b;
    return lhs.c < rhs.c;
}

bool cmp2(const _node &lhs, const _node &rhs) {
    return lhs.b < rhs.b;
}
//  cmp2 用于 cdq 分治

bool operator != (const _node &lhs, const _node &rhs) {
    return (lhs.a != rhs.a) || (lhs.b != rhs.b) || (lhs.c != rhs.c);
} 

int n, k, c[MAXK];

void add(int x, int val) {
    for ( ; x <= k; x += x & (-x))
        c[x] += val;
    return ;
}

int query(int x) {
    int res = 0;
    for ( ; x; x -= x & (-x))
        res += c[x];
    return res;
}

void cdq(int l, int r) {
    if (l == r)
        return ;
    int mid = (l + r) >> 1;
    cdq(l, mid);
    cdq(mid + 1, r);
    sort(node + l, node + mid + 1, cmp2);
    sort(node + mid + 1, node + r + 1, cmp2);
    int j = l;
    for (int i = mid + 1; i <= r; i++) {
        while (j <= mid && node[j].b <= node[i].b) {
            add(node[j].c, 1);
            j++;
        }
        node[i].ans += query(node[i].c);
    }
    while (--j >= l)
        add(node[j].c, -1);
//  attention!!
//  树状数组必须清空，否则凉凉
    return ;
}

int main() {
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d %d %d",&node[i].a, &node[i].b, &node[i].c);
    sort(node + 1, node + n + 1, cmp1);
    for (int i = n, j = n; i >= 1; i--) {
        while (node[i] != node[j])
            j--;
        node[i].ans += j - i;
        printf(" > %d\n", node[i].ans);
    }
//  attention!!
//  特判 i < j 且 a, b, c 全部相等的情况
//  原因：cdq(l, r) 中的第一个 while 会把所有相等的都跳过
    cdq(1, n);
    for (int i = 1; i <= n; ++i)
        cnt[node[i].ans]++;
    for (int i = 0; i < n; i++)
        printf("%d\n", cnt[i]);
    return 0;
}