AcWing 2815. 三维偏序 题解

题目分析

本题给定(n)个元素，每个元素有(a_i)、(b_i)、(c_i)三种属性。定义函数(f(i))表示满足(a_j\leq a_i)、(b_j\leq b_i)、(c_j\leq c_i)且(j\neq i)的(j)的数量。要求对于(d\in[0,n))，求出满足(f(i)=d)的(i)的数量。

解题思路

本题采用分治法结合树状数组来解决三维偏序问题。通过对元素按照第一维属性排序，然后在分治过程中处理第二维和第三维属性，利用树状数组高效地统计满足条件的元素个数。
1. 定义数据结构：定义结构体Data来存储每个元素的三种属性值(a)、(b)、(c)，以及元素的数量(s)和满足条件的数量(res)。
2. 树状数组操作：实现树状数组的基本操作，包括lowbit函数用于计算二进制下的最低位，add函数用于更新树状数组，query函数用于查询前缀和。
3. 归并排序与统计：merge_sort函数通过归并排序，在合并过程中，根据元素的第二维属性进行排序，同时利用树状数组统计第三维属性满足条件的元素个数，从而得到每个元素的(f(i))值。
4. 结果统计与输出：对计算得到的每个元素的(f(i))值进行统计，得到满足(f(i)=d)的(i)的数量，并输出结果。

代码逐段分析

1. 头文件和全局变量定义

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, M = 200010;

int n, m;
struct Data
{
    int a, b, c, s, res;

    bool operator< (const Data& t) const
    {
        if (a != t.a) return a < t.a;
        if (b != t.b) return b < t.b;
        return c < t.c;
    }
    bool operator== (const Data& t) const
    {
        return a == t.a && b == t.b && c == t.c;
    }
}q[N], w[N];
int tr[M], ans[N];

• 引入必要的头文件，包括输入输出、字符串操作和算法相关的头文件。
• 定义常量(N)表示元素的最大数量，(M)用于树状数组的大小。
• 变量(n)表示元素的数量，(m)表示属性值的最大值（题目中未明确其具体用途，推测用于数据范围界定）。
• 定义结构体Data，包含元素的三种属性(a)、(b)、(c)，元素数量(s)（用于处理重复元素），以及满足条件的数量(res)。同时重载了小于号和等于号运算符，方便排序和比较。
• q[N]和w[N]分别用于存储原始元素和归并排序过程中的临时元素。

• tr[M]是树状数组，ans[N]用于存储最终的结果，即满足(f(i)=d)的(i)的数量。

• 树状数组辅助函数

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

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

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

• lowbit函数返回(x)在二进制表示下的最低位，例如(x = 6)（二进制为(110)），则lowbit(6)=2（二进制为(10)）。
• add函数用于在树状数组的位置(x)上加上值(v)，通过不断加上lowbit(i)来更新树状数组的相关位置。

• query函数用于查询树状数组中位置(x)的前缀和，通过不断减去lowbit(i)来累加相关位置的值。

• 归并排序与统计函数

void merge_sort(int l, int r)
{
    if (l >= r) return;
    int mid = l + r >> 1;
    merge_sort(l, mid), merge_sort(mid + 1, r);
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r)
        if (q[i].b <= q[j].b) add(q[i].c, q[i].s), w[k ++ ] = q[i ++ ];
        else q[j].res += query(q[j].c), w[k ++ ] = q[j ++ ];
    while (i <= mid) add(q[i].c, q[i].s), w[k ++ ] = q[i ++ ];
    while (j <= r) q[j].res += query(q[j].c), w[k ++ ] = q[j ++ ];
    for (i = l; i <= mid; i ++ ) add(q[i].c, -q[i].s);
    for (i = l, j = 0; j < k; i ++, j ++ ) q[i] = w[j];
}

• 该函数使用归并排序来处理三维偏序问题。如果(l\geq r)，则说明子数组只有一个元素或为空，直接返回。
• 计算中点mid，并递归地对左右子数组进行归并排序。
• 在合并过程中，通过比较元素的第二维属性(b)：
  • 如果(q[i].b\leq q[j].b)，则将(q[i])的第三维属性(c)和数量(s)加入树状数组，并将(q[i])存入临时数组w。
  • 否则，查询树状数组中小于等于(q[j].c)的元素数量，并累加到(q[j].res)中，然后将(q[j])存入临时数组w。
• 处理完左右子数组后，将左子数组剩余元素加入树状数组，右子数组剩余元素进行统计。

• 清除左子数组在树状数组中的影响（减去相应的值），最后将临时数组w中的元素复制回原数组q。

• 主函数

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        q[i] = {a, b, c, 1};
    }
    sort(q, q + n);

    int k = 1;
    for (int i = 1; i < n; i ++ )
        if (q[i] == q[k - 1]) q[k - 1].s ++ ;
        else q[k ++ ] = q[i];

    merge_sort(0, k - 1);
    for (int i = 0; i < k; i ++ )
        ans[q[i].res + q[i].s - 1] += q[i].s;

    for (int i = 0; i < n; i ++ ) printf("%d\n", ans[i]);

    return 0;
}

• 读入元素数量(n)和属性值最大值(m)，以及每个元素的三种属性值，初始化每个元素的数量为(1)。
• 对元素按照第一维属性(a)进行排序。
• 合并重复元素，统计每个重复元素的数量。
• 调用merge_sort函数进行归并排序和统计，得到每个元素的(f(i))值（存储在res中）。
• 根据每个元素的(f(i))值和数量(s)，统计满足(f(i)=d)的(i)的数量，存入ans数组。
• 输出最终结果，即对于(d\in[0,n))，满足(f(i)=d)的(i)的数量。

时间复杂度分析

• 排序操作的时间复杂度为(O(n\log n))。
• 归并排序过程中，每次合并的时间复杂度为(O(n))，总共递归(\log n)层，所以归并排序的时间复杂度为(O(n\log n))。
• 树状数组的操作时间复杂度为(O(\log m))，在归并排序中对树状数组的操作次数为(O(n))，所以树状数组相关操作的总时间复杂度为(O(n\log m))。
• 总体时间复杂度为(O(n\log n + n\log m))，由于(m)相对(n)通常不会过大，可近似认为时间复杂度为(O(n\log n))。

空间复杂度分析

主要空间消耗在于存储元素的数组、树状数组和临时数组等，空间复杂度为(O(n + m)) 。