众所周知，三维偏序问题除了树套树还可以用CDQ分治来解决

CDQ分治与一般的分治区别之处在于，CDQ分治将一个问题划分为两个子问题的同时，按照特定的顺序解决子问题，先解决的子问题对后解决的子问题产生贡献。

先来一道模板题，又是陌上花开
题面就是一道裸的三维偏序
用CDQ分治解决本题的流程
1.按x轴对所有点排序，划分为左右两部分
2.递归解决左右子问题
3.因为此时右边半个子问题是不包含左边的贡献的，所以对右边需要额外加上左边子问题的贡献
4.对左半部分的点按照y轴排序
//因为此时左半部分点的x轴位置均在右半部分左侧，所以只需要按照y轴区分贡献
5.此时问题就降维成二维偏序了
//用树状数组维护一下就好了

贴代码

// #pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <list>
#include <cstdlib>
#include <bitset>
#include <assert.h>
// #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
// char buf[(1 << 21) + 1], * p1 = buf, * p2 = buf;
//#define int long long
#define lowbit(x) (x & (-x))
#define lson root << 1, l, mid
#define rson root << 1 | 1, mid + 1, r
#define pb push_back
typedef unsigned long long ull;
typedef long long ll;
typedef std::pair<int, int> pii;
#define bug puts("BUG")
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-6;
template <class T>
inline void read(T &x)
{
    int sign = 1;char c = getchar();x = 0;
    while (c > '9' || c < '0'){if (c == '-')sign = -1;c = getchar();}
    while (c >= '0' && c <= '9'){x = x * 10 + c - '0';c = getchar();}
    x *= sign;
}
#ifdef LOCAL
    FILE* _INPUT=freopen("input.txt", "r", stdin);
    // FILE* _OUTPUT=freopen("output.txt", "w", stdout);
#endif
using namespace std;
const int maxn = 1e6 + 10;
struct NODE
{
    int x, y, z, idx, w;
    bool operator < (const NODE& other)const
    {
        if (x != other.x)
            return x < other.x;
        if (y != other.y)
            return y < other.y;
        return z < other.z;
    }
    bool operator == (const NODE& other)const
    {
        return x == other.x && y == other.y && z == other.z;
    }
} f[maxn];
struct BIT
{
    int bit[maxn << 1], up;
    void add(int k, int v)
    {
        for (; k <= up; k += lowbit(k))
            bit[k] += v;
    }

    int query(int k)
    {
        int res = 0;
        for (; k > 0; k -= lowbit(k))
            res += bit[k];
        return res;
    }
} bit;
int ans[maxn], ansout[maxn], a[maxn];
bool cmpy(const NODE& a,const NODE&b)
{
    if (a.y != b.y)
        return a.y <= b.y;
    return a.z < b.z;
}

void cdq(int l, int r)
{
    if (l == r)
        return;
    int mid = l + r >> 1;
    cdq(l, mid);
    cdq(mid + 1, r);
    sort(f + l, f + mid + 1,cmpy);
    sort(f + mid + 1, f + r + 1,cmpy);
    int i = mid + 1, j = l;
    for (; i <= r; ++i)
    {
        while (j <= mid && f[j].y <= f[i].y)
            bit.add(f[j].z, f[j].w), ++j;
        ans[f[i].idx] += bit.query(f[i].z);
    }
    for (i = l; i < j; ++i)
        bit.add(f[i].z, -f[i].w);
}

int main()
{
    int n, k;
    read(n), read(k), bit.up = k;
    for (int i = 1; i <= n; ++i)
        read(f[i].x), read(f[i].y), read(f[i].z), f[i].idx = i;
    sort(f + 1, f + 1 + n);
    int tot = 1;
    f[1].w = 1;
    a[f[1].idx] = f[1].idx;
    for (int i = 2; i <= n; ++i)
    {
        if (f[i] == f[i - 1])
        {}
        else
        {
            f[++tot] = f[i];
        }
        f[tot].w++;
        a[f[i].idx] = f[tot].idx;
    }
    cdq(1, tot);
    for (int i = 1; i <= tot; ++i)
        ans[f[i].idx] += f[i].w;
    for (int i = 1; i <= n; ++i)
    {
        ansout[ans[a[i]] - 1]++;
    }
    for (int i = 0; i < n; ++i)
        printf("%d\n", ansout[i]);
}