Beauty Values - 题解

标签与难度

标签: 贡献法, 计数, 思维转换, 数组, 动态规划难度: 1600

题目大意喵~

你好呀，未来的算法大师！我是你们的向导我，今天我们要挑战一个关于“美学”的有趣问题，喵~

题目是这样的：我们拿到一个长度为 $n$ 的数字序列 $a_1, a_2, \dots, a_n$ 。对于任何一个序列，它的“美丽值”被定义为这个序列中不同元素的个数。

我们的任务，就是计算出给定序列 $a$ 的所有连续子区间的美丽值之和。

举个栗子🌰，假如序列是 [1, 2, 1]：它有这些连续子区间：

[1]，美丽值是 1 (只有元素1)
[2]，美丽值是 1 (只有元素2)
[1]，美丽值是 1 (只有元素1)
[1, 2]，美丽值是 2 (有元素1和2)
[2, 1]，美丽值是 2 (有元素2和1)
[1, 2, 1]，美丽值是 2 (有元素1和2)

所以，密码就是所有美丽值的总和： $1 + 1 + 1 + 2 + 2 + 2 = 9$ 。

现在，我们要写一个程序来算出这个总和，帮助Gromah和LZR破解密码，加油哦！

解题思路分析

一看到要计算“所有子区间”的和，我们最朴素的想法可能是……真的去遍历所有子区间，对吧？

我们可以用两层循环，i 从 0 到 n-1，j 从 i 到 n-1，这样就能枚举出所有的子区间 [i, j]。对于每个子区间，我们再用一个哈希表（或者 std::set）来统计不同元素的个数。

这个方法虽然直观，但是复杂度有点高哦，喵~ 两层循环是 $O(N^2)$ ，内部统计如果用哈希表平均是 $O(N)$ ，总复杂度就是 $O(N^3)$ 。就算优化一下统计，也至少是 $O(N^2 \log N)$ 或者 $O(N^2)$ 的级别。对于 $N$ 很大的情况，肯定会超时的说。

所以，我们需要一种更快的办法！这时候，我的魔法就要登场啦——转换思路！

我们不从“子区间”的角度去求和，而是从“每个元素”的角度去思考，看看每个元素对最终的总和贡献了多少。这种方法叫做贡献法，是一种非常强大的计数技巧，呐！

一个元素 a[i] 什么时候才会对一个子区间 [L, R] 的美丽值产生 +1 的贡献呢？只有当 a[i] 是这个子区间 [L, R] 中第一次出现的那个值时，它才会让美丽值增加。如果 a[i] 在 [L, R] 中已经出现过了，那它就是个“重复”的数字，不会增加美丽值。

好，那么问题就变成了：对于数组中的每一个元素 a[i]，我们需要计算有多少个包含它（即 $L \le i \le R$ ）的子区间 [L, R]，使得 a[i] 是该子区间内其对应数值的首次出现。

为了满足这个“首次出现”的条件，子区间的左端点 L 必须在 a[i] 这个值上一次出现位置的右边。我们用 prev_idx 来表示值 a[i] 上一次出现时的下标。如果 a[i] 是第一次出现，我们可以认为 prev_idx 是 -1。

那么，对于 a[i]，能让它产生贡献的子区间 [L, R] 必须满足以下两个条件：

子区间要包含 i： $L \le i \le R$
a[i] 是 [L, R] 中该值的首次出现： $L > \text{prev\_idx}$

把这两个条件合并一下，就是：

左端点 L 的取值范围是： $\text{prev\_idx} + 1 \le L \le i$
右端点 R 的取值范围是： $i \le R \le n-1$

现在我们来数一数有多少种选择：

L 的选择数量是： $i - (\text{prev\_idx} + 1) + 1 = i - \text{prev\_idx}$ 种。
R 的选择数量是： $(n-1) - i + 1 = n - i$ 种。

根据乘法原理，a[i] 对总美丽值的贡献就是 L 的选择数乘以 R 的选择数。

\text{Contribution}(a[i]) = (i - \text{prev\_idx}) \times (n - i)

这样，我们只需要遍历一次数组，对每个 a[i] 计算它的贡献，然后累加起来就是最终答案啦！为了快速找到 prev_idx，我们可以用一个数组或者哈希表 last_pos 来记录每个数值最后一次出现的下标。

我们再用 [1, 2, 1] (0-based index) 走一遍这个流程： n = 3, a = [1, 2, 1], total_beauty = 0last_pos 初始都为 -1。

i = 0, a[0] = 1:
- prev_idx of 1 is -1。
- 贡献 = $(0 - (-1)) \times (3 - 0) = 1 \times 3 = 3$ 。
- total_beauty = 3。
- 更新 last_pos[1] = 0。
i = 1, a[1] = 2:
- prev_idx of 2 is -1。
- 贡献 = $(1 - (-1)) \times (3 - 1) = 2 \times 2 = 4$ 。
- total_beauty = 3 + 4 = 7。
- 更新 last_pos[2] = 1。
i = 2, a[2] = 1:
- prev_idx of 1 is last_pos[1] = 0。
- 贡献 = $(2 - 0) \times (3 - 2) = 2 \times 1 = 2$ 。
- total_beauty = 7 + 2 = 9。
- 更新 last_pos[1] = 2。

遍历结束，最终答案是 9！和我们手动算的一样，完美，喵~！这种方法只需要一次遍历，时间复杂度是线性的，非常高效！

代码实现

这是我根据上面的思路，精心为你准备的一份代码~ 注释很详细，希望能帮到你哦！

cpp

#include <iostream>
#include <vector>
#include <numeric>

// 定义一个比较大的值，用于 last_pos 数组的大小
// 题目给的 N 最大是 2e5，我们假设数值也在这个范围内
const int MAX_VAL = 200005;

void solve() {
    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    // `last_pos` 数组用来记录每个数值最后一次出现的下标
    // 初始化为 -1，表示所有数都还没出现过
    std::vector<int> last_pos(MAX_VAL, -1);

    long long total_beauty_sum = 0;

    // 遍历数组中的每一个元素
    for (int i = 0; i < n; ++i) {
        // 当前元素的值
        int current_val = a[i];
        
        // 获取这个值上一次出现的下标
        int prev_idx = last_pos[current_val];

        // 计算当前元素 a[i] 的贡献
        // 左端点 L 的选择数：i - prev_idx
        // 右端点 R 的选择数：n - i
        // 注意要用 long long 来计算，防止乘法溢出
        long long contribution = (long long)(i - prev_idx) * (n - i);
        
        // 将贡献累加到总和中
        total_beauty_sum += contribution;

        // 更新这个值最后一次出现的位置为当前下标 i
        last_pos[current_val] = i;
    }

    std::cout << total_beauty_sum << std::endl;
}

int main() {
    // 加速 C++ IO，让程序跑得更快，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    // 本题只有一个测试用例
    solve();

    return 0;
}

复杂度分析

时间复杂度: $O(N)$ 我们只对输入数组 a 进行了一次单层循环。在循环的每一步中，我们都只进行了常数时间的数组访问和数学运算。所以，总的时间复杂度是线性的，即 $O(N)$ ，其中 $N$ 是序列的长度。
空间复杂度: $O(N + V)$ 我们使用了 a 数组来存储输入，大小为 $N$ 。此外，我们还用了一个 last_pos 数组来记录每个数值最后出现的位置，其大小 $V$ 取决于输入数值的范围（在代码中我们设为 MAX_VAL）。所以总的空间复杂度是 $O(N + V)$ 。如果数值范围很大，可以使用 std::map 或 std::unordered_map，空间复杂度会变为 $O(N)$ ，但时间复杂度会略微增加到 $O(N \log V)$ 或 $O(N)$ （平均）。

知识点总结

这道题真是一次愉快的思维探险呢！我们来总结一下学到了什么吧，喵~

贡献法 (Contribution Method): 这是解决计数问题的利器！当直接枚举对象（如此题中的子区间）太复杂时，可以尝试转换视角，计算每个基本单元（如此题中的元素）对最终结果的贡献。
思维转换: 从 "求所有子区间的属性和" 转换为 "求每个元素对所有子区间的贡献和"，是解题的关键一步。很多算法问题都需要这样灵活地切换思考角度。
高效查找: 为了实现 $O(N)$ 的解法，我们需要快速得到一个值上一次出现的位置。使用一个辅助数组或哈希表（last_pos）是实现这一点的经典做法。

希望这篇题解能让你对算法有更深的喜爱！下次遇到难题，也试着像我一样，换个角度思考，说不定就能找到奇妙的解法哦！继续加油，喵~！

Beauty Values - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

代码实现 ​

复杂度分析 ​