题目链接：洛谷P3810-陌上花开

题意：

有n个物品，每个物品有三个参数，设F(i)表示满足a(j)<=a(i),b(j)<=b(i),c(j)<=c(i)的数量。对于0<=d<n，求f(i)=d的数量。

题解：

三维偏序。

第一维对a排序；第二维归并排序，因为已经按a排过序，在左边和右边对b排序时仍保证左边的a小于右边；第三维树状数组，查询满足前两位偏序关系，且c小于当前数的个数。

注意一点，因为我们把完全相同的物品进行了缩点，计算贡献时需要减1.

参考代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
const int MAXK = 2e5 + 5;
int n, k;
int tot = 0;
unordered_map<ll, int> mp;
ll getid(ll x, ll y, ll z) { return 1ll * x * MAXK * MAXK + 1ll * y * MAXK + 1ll * z; }
struct NODE
{
    int x, y, z, v, ans;
    NODE() {}
    NODE(int x, int y, int z, int v, int ans)
    {
        this->x = x, this->y = y, this->z = z, this->v = v, this->ans = ans;
    }
} a[MAXN];
bool cmp1(NODE x, NODE y) { return (x.x == y.x) ? ((x.y == y.y) ? x.z < y.z : x.y < y.y) : x.x < y.x; }
struct BIT
{
    int c[MAXK], _n;
    void init(int _n)
    {
        for (int i = 1; i <= _n; i++)
            c[i] = 0;
        this->_n = _n;
    }
    int lowbit(int x)
    {
        return x & -x;
    }
    /* 单点修改 区间求和 */
    void update(int x, int val)
    {
        while (x <= _n)
        {
            c[x] += val;
            x += lowbit(x);
        }
    }
    int getsum(int x)
    {
        int ret = 0;
        while (x)
        {
            ret += c[x];
            x -= lowbit(x);
        }
        return ret;
    }
} bit;
bool cmp2(NODE x, NODE y) { return x.y == y.y ? x.z < y.z : x.y < y.y; }
void cdq(int l, int r)
{
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    cdq(l, mid);
    cdq(mid + 1, r);
    sort(a + l, a + mid + 1, cmp2);
    sort(a + mid + 1, a + r + 1, cmp2);
    int p = l, q = mid + 1;
    for (; q <= r; q++)
    {
        while (a[p].y <= a[q].y && p <= mid)
            bit.update(a[p].z, a[p].v), p++;
        a[q].ans += bit.getsum(a[q].z);
    }
    for (int i = l; i < p; i++)
        bit.update(a[i].z, -a[i].v);
}
int cnt[MAXN];
int main()
{
    scanf("%d%d", &n, &k);
    mp.clear();
    tot = 0;
    for (int i = 1; i <= n; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        if (mp.count(getid(x, y, z)))
        {
            int pp = a[mp[getid(x, y, z)]].v + 1;
            a[mp[getid(x, y, z)]] = NODE(x, y, z, pp, 0);
        }
        else
            mp[getid(x, y, z)] = ++tot, a[tot] = NODE(x, y, z, 1, 0);
    }
    sort(a + 1, a + 1 + tot, cmp1);
    bit.init(k);
    cdq(1, tot);
    for (int i = 1; i <= tot; i++)
        cnt[a[i].ans + a[i].v - 1] += a[i].v;
    for (int i = 0; i < n; i++)
        printf("%d\n", cnt[i]);
    return 0;
}