Moe's CF Life

Appearance

E. Power of Points - 题解 ​

比赛与标签 ​

比赛: Codeforces Round 891 (Div. 3) 标签: math, sortings 难度: *1500

题目大意喵~ ​

主人你好呀~！这道题是这样的喵：

我们有一条数轴和上面 n 个点，坐标分别是 x_1, x_2, ..., x_n。现在，我们要从这 n 个点里轮流选一个点作为特殊点 s。

对于每一个选定的 s，我们都会生成 n 条线段：[s, x_1], [s, x_2], ..., [s, x_n]。如果 x_i 比 s 小，那么线段就是 [x_i, s] 啦。

接着，我们定义一个点 p 的“能量值” f_p，它等于覆盖了点 p 的线段数量。

我们的任务是，对于每个 s（s 会依次取遍所有输入的 x_i），计算出所有整数点（从 1 到 10^9）的能量值之和，也就是 Σ f_p。

最后，按照输入 x_i 的顺序，输出每个 s 对应的能量值总和。是不是很有趣的说？

解题思路喵~ ​

呐, 主人, 这个问题看起来有点绕，直接计算每个点的能量值再求和肯定会超时的说。所以我们要换个思路，把它变成一只温顺的小猫咪喵~

关键的转换！ ​

我们要求的 Σ f_p 是什么呢？f_p 是覆盖点 p 的线段数。我们可以把这个求和顺序换一下，不先算每个点的能量，而是先看每条线段对总能量和的贡献。

总能量和 Σ f_p = Σ_p (Σ_{j=1 to n} [点 p 在线段 [s, x_j] 上])

交换一下求和符号，就变成了：

Σ_{j=1 to n} (Σ_p [点 p 在线段 [s, x_j] 上])

后面的 (Σ_p [点 p 在线段 [s, x_j] 上]) 是什么意思呢？它其实就是计算线段 [s, x_j] 覆盖了多少个整数点。一条从 a 到 b（假设 a <= b）的线段，覆盖的整数点数量就是 b - a + 1，也就是 |s - x_j| + 1 啦！

所以，对于一个固定的 s，总能量和就等于所有线段覆盖的整数点数量之和：

Σ f_p = Σ_{j=1 to n} (|s - x_j| + 1)

这个式子可以进一步拆开：

Σ f_p = (Σ_{j=1 to n} |s - x_j|) + (Σ_{j=1 to n} 1) = (Σ_{j=1 to n} |s - x_j|) + n

哇！问题一下子清晰了！我们只需要对每个给定的 s，快速计算出 Σ |s - x_j|，然后加上 n 就是答案了喵！

如何快速计算 Σ |s - x_j|？ ​

如果每次都遍历一遍所有的 x_j 来计算和，总时间复杂度会是 O(n^2)，对于 n 高达 2e5 的情况还是太慢了。这里有一个经典的优化技巧：排序 + 前缀和！

  1. 排序：我们先把所有的坐标点 x 进行排序，得到一个新的数组 sorted_x。

  2. 拆分绝对值：对于一个 s 和排好序的 sorted_x，Σ |s - x_j| 可以被拆成两部分：

    • 所有 x_j <= s 的点，|s - x_j| 就等于 s - x_j。
    • 所有 x_j > s 的点，|s - x_j| 就等于 x_j - s。

  3. 前缀和加速：为了快速得到某一段 x_j 的和，我们可以预先计算 sorted_x 的前缀和数组 prefix。prefix[k] 表示 sorted_x 前 k 个元素的和。

现在，假设我们已经知道在 sorted_x 中，有 pos 个点是小于等于 s 的。我们可以用二分查找（比如 C++ 的 upper_bound）很快地找到这个 pos。

  • 对于小于等于 s 的 pos 个点：

    • 它们的和是 Σ_{j=1 to pos} (s - sorted_x_j) = pos * s - (Σ_{j=1 to pos} sorted_x_j)。
    • Σ_{j=1 to pos} sorted_x_j 就是 prefix[pos]。
    • 所以这部分的和是 pos * s - prefix[pos]。

  • 对于大于 s 的 n - pos 个点：

    • 它们的和是 Σ_{j=pos+1 to n} (sorted_x_j - s) = (Σ_{j=pos+1 to n} sorted_x_j) - (n - pos) * s。
    • Σ_{j=pos+1 to n} sorted_x_j 就是 prefix[n] - prefix[pos]。
    • 所以这部分的和是 (prefix[n] - prefix[pos]) - (n - pos) * s。

把这两部分加起来，就得到了 Σ |s - x_j| 的值。最后别忘了加上 n 哦！

完整流程 ​

  1. 读入 n 和 n 个坐标 x。
  2. 创建一个 x 的副本 sorted_x 并对其进行排序。
  3. 基于 sorted_x 计算前缀和数组 prefix。
  4. 遍历原始的 x 数组（为了保证输出顺序正确），将每个 x[i] 作为当前的 s。
  5. 对于每个 s，使用 upper_bound 在 sorted_x 中找到分界点 pos。
  6. 利用 pos 和前缀和数组，套用上面的公式计算出 Σ |s - x_j|。
  7. 将结果加上 n，然后输出。

这样，每次计算一个 s 的答案只需要 O(log n) 的时间，总的时间复杂度就是 O(n log n)，完全可以接受啦！

代码实现喵~ ​

cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    // 加速输入输出，让程序跑得更快喵~
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<long long> x(n);
        for (int i = 0; i < n; i++) {
            cin >> x[i];
        }

        // 创建一个 x 的副本用于排序，这样就不会打乱原始的顺序了
        vector<long long> sorted_x = x;
        sort(sorted_x.begin(), sorted_x.end());

        // 计算排序后数组的前缀和，方便后面快速求区间和
        // prefix[i] 存储 sorted_x[0] 到 sorted_x[i-1] 的和
        vector<long long> prefix(n + 1, 0);
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + sorted_x[i];
        }

        long long total_sum = prefix[n]; // 所有点的坐标总和

        // 遍历原始的 x 数组，保证输出顺序和输入一致
        for (int i = 0; i < n; i++) {
            long long s = x[i];
            
            // 使用 upper_bound 找到第一个大于 s 的元素的位置
            // 这个位置的索引 'pos' 也就是小于等于 s 的点的数量
            auto it = upper_bound(sorted_x.begin(), sorted_x.end(), s);
            int pos = it - sorted_x.begin();

            // 计算 s 左边的点（小于等于 s 的点）
            long long left_count = pos;
            long long left_sum = prefix[pos]; // 它们在 sorted_x 中的和

            // 计算 s 右边的点（大于 s 的点）
            long long right_count = n - pos;
            long long right_sum = total_sum - left_sum; // 它们在 sorted_x 中的和

            // 根据我们推导的公式计算 Σ|s - x_j|
            // (s * left_count - left_sum) 是 s 与左边点的距离和
            // (right_sum - s * right_count) 是 s 与右边点的距离和
            long long abs_sum = (s * left_count - left_sum) + (right_sum - s * right_count);
            
            // 最终答案是 Σ|s - x_j| + n
            long long ans = n + abs_sum;

            cout << ans;
            if (i < n - 1) {
                cout << " ";
            }
        }
        cout << "\n";
    }
    return 0;
}

复杂度分析喵~ ​

  • 时间复杂度: O(N log N) 的说。 其中，对坐标数组 x 进行排序需要 O(N log N)。计算前缀和需要 O(N)。之后，我们遍历 n 个原始坐标，对每个坐标 s，使用 upper_bound 在排序数组中查找位置需要 O(log N)。所以主循环的总时间是 O(N log N)。合起来，总的时间复杂度就是 O(N log N) 啦，非常高效！

  • 空间复杂度: O(N) 的说。 我们需要额外的空间来存储原始坐标数组 x、排序后的数组 sorted_x 和前缀和数组 prefix。它们的大小都和 N 成正比，所以空间复杂度是 O(N)。

知识点与总结喵~ ​

这道题真是一次愉快的思维体操呢！主人你看，我们学到了：

  1. 问题转化: 这是解题的灵魂所在！把一个看起来很复杂的求和 Σ f_p，通过交换求和顺序，转化为了一个更简洁、更有规律的数学表达式 (Σ |s - x_j|) + n。以后遇到复杂的求和问题，可以多想想能不能从不同角度来计算贡献喵。

  2. 排序 + 前缀和: 这是一个超级经典的组合技！当问题涉及到在有序序列上求和、求差、求区间信息时，这个组合拳往往能打出奇效，将 O(N^2) 的暴力解法优化到 O(N log N) 或 O(N)。

  3. 绝对值和的处理: Σ|A - x_i| 这种形式的和，通过排序将 x_i 分成 < A 和 > A 两部分来去掉绝对值，是一个标准处理技巧。

  4. upper_bound 的妙用: 在有序数组中快速找到第一个大于某个值的元素，这正是我们划分左右两部分所需要的，比自己手写二分要方便多啦。

希望这篇题解能帮到主人哦！下次遇到类似的题目，一定能更快地想到解法啦！加油喵~！

Released under the MIT License.

Copyright © 2024-present Moe