$\Huge{cdq分治}$

$前言$

前置知识：树状数组、归并排序、双指针

$题意$

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

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

$思路$

先将序列按$a_i$排序

利用归并排序思想，将区间分为前半段和后半段

所有可行点对$(i,j)$被分为$3$类：

• $l\leq i < j \leq mid$
• $mid + 1 \leq i < j \leq r$
• $l \leq i \leq mid, mid + 1 \leq j \leq r$

对于前两类，可以递归求解，并顺便将两端按$b_i$排序

由于一开始按$a_i$排序，所以$l \leq i \leq mid, mid + 1 \leq j \leq r$时，$a_i \leq a_j$

所以不用考虑属性$a$

利用双指针算法，如果$b_i \leq b_j$，那么$b_i \leq b_{j+1}$

对于每一个$i$，使得$b_i \leq b_j$，那么就存入树状数组的$c_i$位置

对于每一个$j$，$ans_j=\sum_{l\leq i\leq mid} [b_i \leq b_j][c_i \leq c_j]$，用树状数组查询$c_j$即可

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

$实现$

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 100010, M = 200010;
int n, m;
int tr[N], ans[N];

struct Node {
    int a, b, c, s, res;
    bool operator< (const Node &q) const{
        if (a != q.a) return a < q.a;
        if (b != q.b) return b < q.b;
        return c < q.c;
    }
    bool operator== (const Node &q) const {
        return (a == q.a && b == q.b && c == q.c);
    }
} y[N], w[N];

int lowbit(int i)
{
    return i & -i;
}

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

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

void merge(int l, int r)
{
    if (l >= r) return ;
    int mid = l + r >> 1;
    merge(l, mid), merge(mid + 1, r); //递归
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r)
        if (y[i].b <= y[j].b) add(y[i].c, y[i].s), w[k ++ ] = y[i ++ ]; //树状数组加入
        else y[j].res += query(y[j].c), w[k ++ ] = y[j ++ ]; //树状数组查询
    while (i <= mid) add(y[i].c, y[i].s), w[k ++ ] = y[i ++ ];
    while (j <= r) y[j].res += query(y[j].c), w[k ++ ] = y[j ++ ];
    for (int i = l; i <= mid; i ++ ) add(y[i].c, -y[i].s); //清空数组
    for (int i = l; i <= r; i ++ ) y[i] = w[i]; //粘贴归并结果
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ) 
    {
        scanf("%d%d%d", &y[i].a, &y[i].b, &y[i].c);
        y[i].s = 1;
    }
    sort(y, y + n); //按a属性排序
    int j = 0;
    for (int i = 1; i < n; i ++ )
        if (y[i] == y[j]) y[j].s ++ ;
        else y[++ j] = y[i];
    merge(0, j);
    for (int i = 0; i <= j; i ++ ) ans[y[i].res + y[i].s - 1] += y[i].s;
    for (int i = 0; i < n; i ++ ) printf("%d\n", ans[i]);
    return 0;
}