题目描述

对于数组 $a = (a_1, a_2, ..., a_n)$，$f(a)$ 函数定义为进行完以下操作后数组 $a$ 的元素和。

以 i = 1, 2, 3, ..., k 的顺序进行以下操作：

对 $a_i$ 加上当前 $a$ 数组的最大值。

现在给定长度为 N 的数组 $a = (a_1, a_2, ..., a_N)$，分别计算 $a$ 的子数组 $A_i = (a_1, a_2, ..., a_i)$ 的 $f(A_i)$ 的函数值

输入

第一行为 N $(1 \leqslant N \leqslant 10^5)$

第二行有 N 个数，给出数组 $a$ $(1 \leqslant a_i \leqslant 10^9)$

输出

每一行输出一个数 $f(A_i)$

样例

-输入：

3
1 2 3

-输出：

2
8
19

样例解释

对于 $a$ 的子数组 $A_3$，$f(A_3)$ 的计算过程如下：

s1. 首先对于 i = 1，现在的最大值为 3，则 a1 = 1 + 3，数组变为 A3 = (4, 2, 3)

s2. 然后对于 i = 2，现在的最大值为 4，则 a2 = 2 + 4，数组变为 A3 = (4, 6, 3)

s3. 最后对于 i = 3，现在的最大值为 6，则 a3 = 3 + 6，数组变为 A3 = (4, 6, 9)

最后的 $f(A_3) = 4 + 6 + 9 = 19$

算法：前缀和

不难发现，每一次的操作都是加上数组的最大值，因此从第一次加了最大值开始，整个数组的最大值就顺次变成了 $a_1, a_2, ...,$ 因此我们考虑用前缀和。具体操作如下：

1. 预处理前缀和，并用一个变量 k 表示当前最大元素下标。
2. 若已经遍历到第 i 个元素，则当前的 $f(A_i)$ 首先需要加上前缀和 $s_i$，因为函数 f 求的就是一个前缀和，这么做相当于把前缀和除了 $a_i$ 的部分拷贝了一遍并翻倍；而后判断当前元素 $a_i$ 是否严格大于之前的最大元素 $a_k$，如果是，说明之前的最大值我们不能加，只能存在于之前累加好的前缀和中，并且当前最大值需要加 i 遍，同时更新最大元素下标 k。
3. 若在 2 中，当前元素 $a_i \leqslant a_k$，则最大值还是 $a_k$，因此只需要加上一个最大值就能达到最大值被加了 i 次。

时间复杂度 $O(n)$

C++ 代码

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

using namespace std;

typedef long long LL;

const int N = 200010;

int n;
int a[N];
LL s[N], ans;

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i]; 

    for (int i = 1, k = 0; i <= n; i ++ )
    {
        ans += s[i];
        if (a[k] < a[i])
        {
            ans -= (LL)a[k] * (i - 1);
            ans += (LL)a[i] * i;
            k = i;
        }
        else ans += a[k];
        printf("%lld\n", ans);
    }

    return 0;
}