CF1990C Mad MAD Sum 题解

题意回顾

给定长度为 $n$ 的数组 $a$，初始 $sum=0$。重复以下过程直至 $a$ 全为 $0$：

1. $sum \mathrel{+}= \sum_{i=1}^n a_i$；
2. 对每个 $i$，令 $b_i = \operatorname{MAD}(a_1,\dots,a_i)$，然后将 $a_i$ 赋值为 $b_i$。

其中 $\operatorname{MAD}$ 表示前缀中出现至少两次的最大数字，若不存在则为 $0$。

求最终 $sum$ 的值。$n$ 总和 $\le 2\times 10^5$，$t \le 2\times 10^4$。

核心观察（手模大样例）

以数组 $[1,1,4,2,2,4,9,9,9,0]$ 为例，逐次变换如下：

初始:  1  1  4  2  2  4  9  9  9  0
第1次: 0  1  1  1  2  4  4  9  9  9
第2次: 0  0  1  1  1  1  4  4  9  9
第3次: 0  0  0  1  1  1  1  4  4  9
第4次: 0  0  0  0  1  1  1  1  4  4
第5次: 0  0  0  0  0  1  1  1  1  4
...

观察规律：

1. 第 1 次变换后，数组变成非严格递增的若干等值段，非末尾段中可能出现长度为 $1$ 的段。
2. 第 2 次变换后，除末尾段外所有段的长度都 $>1$，且整个序列的变换规律固定下来。
3. 从第 3 次变换开始，序列等价于整体向右平移一格（最左侧补 $0$），每个非零值依次向右"流动"，直到从右端移出。

因此可以：

• 直接模拟前两次变换；
• 之后不再逐次模拟，而是利用"每个值在后续操作中会贡献 $n-i$ 次"的结论一次性计算。

算法流程

1. 读入原始数组，累加其总和。
2. 执行第一次 MAD 变换：
   • 维护 $awa$ = 当前前缀中至少出现两次的最大值。
   • 用集合（或计数数组）记录已出现过的值。若当前值已在集合中，则更新 $awa = \max(awa, a_i)$。
   • 令 $a_i = awa$（即 $b_i$），同时 $sum \mathrel{+}= a_i$。
3. 清空集合，重复上述过程完成第二次 MAD 变换。
4. 此时数组处于稳定状态。累加 $\sum_{i=1}^n (n-i) \cdot a_i$。
5. 输出 $sum$。

为什么是 $n-i$？
稳定后位置 $i$ 的值在后续每次变换中向右移动一格。它将依次出现在位置 $i+1, i+2, \dots, n$，参与对应轮次的求和。共 $n-i$ 次，每次贡献 $a_i$。

复杂度

• 每次 MAD 变换只需一趟扫描，每轮 $O(n\log n)$（若用 set）或 $O(n)$（若用计数数组，值域 $\le n$）。
• 总复杂度 $O(\sum n \log n)$ 或 $O(\sum n)$，足以通过。

参考代码

#include <set>
#include <iostream>
#define int long long
using namespace std;

int t, n, sum, num[200005];
set<int> so;

void solve() {
    cin >> n;
    sum = 0;
    int awa = 0;
    so.clear();

    for (int i = 1; i <= n; i++) {
        cin >> num[i];
        sum += num[i];                     // 初始数组和
    }

    // 第一次 MAD 变换
    for (int i = 1; i <= n; i++) {
        if (so.find(num[i]) != so.end())
            awa = max(awa, num[i]);
        so.insert(num[i]);
        num[i] = awa;
        sum += awa;
    }

    // 第二次 MAD 变换
    so.clear();
    awa = 0;
    for (int i = 1; i <= n; i++) {
        if (so.find(num[i]) != so.end())
            awa = max(awa, num[i]);
        so.insert(num[i]);
        num[i] = awa;
        sum += awa;
    }

    // 稳定后的贡献
    for (int i = 1; i <= n; i++)
        sum += (n - i) * num[i];

    cout << sum << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> t;
    while (t--) solve();
    return 0;
}