AcWing 2847. 老C的任务 题解

题目分析

本题要求实现一个手机基站管理系统的查询功能，给定(n)个基站的坐标和功率，以及(m)次查询，每次查询一个矩形区域，需要返回该区域内所有基站的功率总和。如果区域内没有基站，则返回(0)。

解题思路

本题采用二维偏序的思想，通过归并排序来解决。将基站和查询区域都转化为数据结构，利用归并排序过程中的顺序处理，高效地统计出每个查询区域内的基站功率总和。
1. 定义数据结构：定义结构体Data来存储基站和查询区域的相关信息，包括坐标(x)、(y)，类型标识(z)（(0)表示基站，(1)表示查询区域），功率(p)，查询编号(id)（查询区域才有），符号标识(sign)（用于计算查询区域的功率总和），以及临时存储的功率总和(sum)。
2. 归并排序：merge_sort函数通过归并排序，在合并过程中，根据(y)坐标进行排序，同时统计基站功率，计算每个查询区域内的功率总和。
3. 输入处理与计算：读入基站和查询区域的信息，将它们转化为结构体并存储。对所有数据进行排序后，调用归并排序函数进行计算。最后根据计算结果输出每个查询的答案。

代码逐段分析

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

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

using namespace std;

typedef long long LL;

const int N = 500010;

int n, m;
struct Data
{
    int x, y, z, p, id, sign;
    LL sum;

    bool operator< (const Data& t) const
    {
        if (x != t.x) return x < t.x;
        if (y != t.y) return y < t.y;
        return z < t.z;
    }
}q[N], w[N];
LL ans[N];

• 引入必要的头文件，包括输入输出、字符串操作和算法相关的头文件。
• 定义LL为long long的别名。
• 定义常量(N)表示数据的最大数量。
• 变量(n)表示基站的数量，(m)表示查询的次数。
• 定义结构体Data，包含坐标(x)、(y)，类型标识(z)（(0)表示基站，(1)表示查询区域），功率(p)，查询编号(id)（查询区域才有），符号标识(sign)（用于计算查询区域的功率总和），以及临时存储的功率总和(sum)。同时重载了小于号运算符，方便排序。
• q[N]和w[N]分别用于存储原始数据和归并排序过程中的临时数据。

• ans[N]用于存储每个查询的结果，即查询区域内的基站功率总和。

• 归并排序函数

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;
    LL sum = 0;
    while (i <= mid && j <= r)
        if (q[i].y <= q[j].y) sum += !q[i].z * q[i].p, w[k ++ ] = q[i ++ ];
        else q[j].sum += sum, w[k ++ ] = q[j ++ ];
    while (i <= mid) sum += !q[i].z * q[i].p, w[k ++ ] = q[i ++ ];
    while (j <= r) q[j].sum += sum, w[k ++ ] = q[j ++ ];
    for (i = l, j = 0; j < k; i ++, j ++ ) q[i] = w[j];
}

• 该函数使用归并排序来处理数据。如果(l\geq r)，则说明子数组只有一个元素或为空，直接返回。
• 计算中点mid，并递归地对左右子数组进行归并排序。
• 在合并过程中，通过比较元素的(y)坐标：
  • 如果(q[i].y\leq q[j].y)，并且(q[i])是基站（(q[i].z == 0)），则将其功率累加到(sum)中，然后将(q[i])存入临时数组w。
  • 否则，说明遇到查询区域，将当前累计的功率(sum)累加到查询区域的(sum)属性中，然后将(q[j])存入临时数组w。
• 处理完左右子数组后，将左子数组剩余的基站功率加入(sum)，右子数组剩余的查询区域进行功率累加。

• 最后将临时数组w中的元素复制回原数组q。

• 主函数

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ )
    {
        int x, y, p;
        scanf("%d%d%d", &x, &y, &p);
        q[i] = {x, y, 0, p};
    }
    int k = n;
    for (int i = 1; i <= m; i ++ )
    {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        q[k ++ ] = {x2, y2, 1, 0, i, 1};
        q[k ++ ] = {x1 - 1, y2, 1, 0, i, -1};
        q[k ++ ] = {x2, y1 - 1, 1, 0, i, -1};
        q[k ++ ] = {x1 - 1, y1 - 1, 1, 0, i, 1};
    }

    sort(q, q + k);
    merge_sort(0, k - 1);

    for (int i = 0; i < k; i ++ )
        if (q[i].z)
            ans[q[i].id] += q[i].sum * q[i].sign;

    for (int i = 1; i <= m; i ++ ) printf("%lld\n", ans[i]);
    return 0;
}

• 读入基站数量(n)和查询次数(m)，以及每个基站的坐标和功率，将基站信息存入数组q，类型标识设为(0)。
• 读入每个查询区域的坐标，将查询区域转化为四个边界点（利用容斥原理），并赋予相应的类型标识(1)、查询编号(id)和符号标识(sign)，存入数组q。
• 对所有数据按照(x)、(y)、(z)的顺序进行排序。
• 调用merge_sort函数进行归并排序和计算。
• 遍历所有数据，对于查询区域（(q[i].z == 1)），根据其符号标识(sign)和计算得到的功率总和(sum)，更新答案数组ans。
• 输出每个查询的结果，即查询区域内的基站功率总和。

时间复杂度分析

• 排序操作的时间复杂度为(O((n + 4m)\log(n + 4m)))，因为总共处理(n)个基站和(4m)个查询区域边界点。
• 归并排序过程中，每次合并的时间复杂度为(O(n + 4m))，总共递归(\log(n + 4m))层，所以归并排序的时间复杂度为(O((n + 4m)\log(n + 4m)))。
• 总体时间复杂度为(O((n + 4m)\log(n + 4m)))。

空间复杂度分析

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