原题

给定长度为 n 的数字序列 a_1,a_2,...,a_n。令 f_i 表示 a_1,...,a_i 中的最大值，g_i 表示 a_1,...,a_i 中的最小值，求

$$ \sum_{i=1}^{n}(f_i+g_i). $$

输入第一行是整数 n (1<=n<=10^5)；第二行是 n 个整数 a_1,...,a_n (1<=a_i<=10^4)。

输出一行一个整数，表示答案。

样例：

输入
1
1

输出
2

题解

MC0441 折扇游戏（C++17）

对每个前缀 [1,i]，题目定义 f_i 为前缀最大值、g_i 为前缀最小值，要求 Σ(f_i+g_i)。顺着输入扫一遍，就能把每个前缀的两个极值求出来。

从前缀 [1,i-1] 走到 [1,i]，只多了 a_i 这一个数。它要么改写当前最大值或最小值，要么什么也不改变：

$$ f_i=\max(f_{i-1},a_i),\qquad g_i=\min(g_{i-1},a_i). $$

若 a_i 更大，它成为新的最大值；最小值同理。相等时极值不变，但这个前缀的 f_i+g_i 仍然要加进答案。

扫到第 i 个数后，mx=f_i、mn=g_i，把 mx+mn 加到 ans。第一个元素后两者都会变成 a_1，单元素数组自然也能处理。

每个前缀恰在其右端点读入后贡献一次，因此 ans 正好是所求和。

时间复杂度为 O(n)，空间复杂度为 O(1)。n<=10^5，答案使用 long long 保存。

代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    int mx = 0;
    int mn = 1000000000;
    long long ans = 0;

    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        mx = max(mx, x);
        mn = min(mn, x);
        ans += mx + mn;
    }

    cout << ans << '\n';
    return 0;
}

实现核对

mx、mn 分别对应 f_i,g_i；ans 对应 Σ_{i=1}^n(f_i+g_i)。