洛谷 P3810 【模板】三维偏序（陌上花开）

【模板】三维偏序（陌上花开）

题目描述

有 $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\ne i$ 的 $j$ 的数量。

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

输入格式

第一行两个整数 $n,k$，表示元素数量和最大属性值。

接下来 $n$ 行，每行三个整数 $a_i,b_i,c_i$，分别表示三个属性值。

输出格式

$n$ 行，第 $d+1$ 行表示 $f(i)=d$ 的 $i$ 的数量。

样例 #1

样例输入 #1

10 3
3 3 3
2 3 3
2 3 1
3 1 1
3 1 2
1 3 1
1 1 2
1 2 2
1 3 2
1 2 1

样例输出 #1

3
1
3
0
1
0
1
0
0
1

数据规模与约定

$1\le n\le 10^5$，$1\le a_i,b_i,c_i\le k\le 2\times 10^5$。

原题

洛谷P3810——传送门

思路

很遗憾，本蒟蒻尚不具备自己想出该紫题思路的能力，所以思路借鉴的是 echo6342 大佬的题解，并给出了自己实现的代码。思路详见洛谷题解——传送门的 echo6342 大佬写的题解。不过本蒟蒻会努力的喵，争取提高自己的能力uuu。

代码

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

const int maxn = 1e5 + 6;
const int maxk = 2e5 + 6;

int n, kk;

struct node
{
    int x, y, z;
    int w;   // 权值，其值表示的是该元素的重复数量
    int ans; // 统计有多少个x,y,z均小于等于本元素的元素数量
    bool operator==(const node &a) const
    {
        return x == a.x && y == a.y && z == a.z;
    }
    void operator=(const node &a)
    {
        x = a.x;
        y = a.y;
        z = a.z;
        w = a.w;
        ans = a.ans;
    }
};

node b[maxn]; // 输入的元素数组
node a[maxn]; // 去重后的元素数组

int cnt[maxk]; // 统计答案个数

int tr[maxn]; // 树状数组

int lowbit(int x) // 获取低位2次幂数
{
    return x & -x;
}

void update(int x, int k) // 单点修改
{
    while (x <= kk)
    {
        tr[x] += k;
        x += lowbit(x);
    }
}

int query(int x) // 前缀和查询
{
    int res = 0;
    while (x)
    {
        res += tr[x];
        x -= lowbit(x);
    }
    return res;
}

bool cmp_x(node a, node b)
{
    if (a.x == b.x)
        if (a.y == b.y)
            return a.z < b.z;
        else
            return a.y < b.y;
    else
        return a.x < b.x;
}

bool cmp_y(node a, node b)
{
    if (a.y == b.y)
        if (a.z == b.z)
            return a.x < b.x;
        else
            return a.z < b.z;
    else
        return a.y < b.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, cmp_y);
    sort(a + mid + 1, a + r + 1, cmp_y);

    // 双指针，j指向前一半，i指向后一半
    int j = l;
    for (int i = mid + 1; i <= r; i++)
    {
        while (a[j].y <= a[i].y && j <= mid)
        {
            update(a[j].z, a[j].w);
            j++;
        }
        a[i].ans += query(a[i].z);
    }
    // 清空树状数组
    for (int i = l; i < j; i++)
    {
        update(a[i].z, -a[i].w);
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> kk;

    for (int i = 1; i <= n; i++)
    {
        cin >> b[i].x >> b[i].y >> b[i].z;
        b[i].w = 1;
        b[i].ans = 0;
    }
    // 按第一维排序
    sort(b + 1, b + 1 + n, cmp_x);

    // 去重，将b数组转化为a数组，同时更新n的值
    int last_n = n;
    int new_n = 0;
    for (int i = 1; i <= last_n; i++)
    {
        if (b[i] == b[i - 1]) // 结构体中已重载==运算符
        {
            a[new_n].w++;
        }
        else
        {
            new_n++;
            a[new_n] = b[i]; // 结构体中已重载=运算符
        }
    }
    n = new_n; // 更新n的值为去重后数组即a数组的大小

    cdq(1, n); // 分治喵

    for (int i = 1; i <= n; i++)
    {
        cnt[a[i].ans + a[i].w - 1] += a[i].w; // 按照题目要求统计数量
    }
    for (int i = 0; i < last_n; i++)
    {
        cout << cnt[i] << '\n';
    }

    return 0;
}