📝 题目大意

对于序列 $a = (a_1, \dots, a_k)$，依次对 $i=1,2,\dots,k$ 执行：将当前序列的最大值加到 $a_i$ 上。定义 $f(a)$ 为操作结束后所有元素之和。给定长度为 $N$ 的数组 $A$，对每个 $k=1,\dots,N$，求前缀 $a = (A_1,\dots,A_k)$ 的 $f(a)$。

💡 解题思路

1. 题目分析：$N \leq 2\times 10^5$ 意味着每个 $k$ 必须 $O(1)$ 或均摊 $O(1)$ 回答。暴力模拟每次操作是 $O(k^2)$，不可行。需要挖掘操作过程中最大值的变化规律，推导封闭公式。

2. 算法推导：

   • 设前缀长度为 $k$，初始最大值为 $M = \max(A_1, \dots, A_k)$，前缀和记为 $S_i = \sum_{j=1}^{i} A_j$（约定 $S_0 = 0$）。
   • 观察每次操作后最大值的变化：
     • 第 $1$ 步：当前 $\max$ 为 $M$，加到 $a_1$ 上，$a_1$ 变为 $A_1 + M$。新 $\max$ 为 $\max(A_1+M, A_2, \dots, A_k) = A_1 + M = M + S_1$（因为 $A_1 \ge 1$，故 $A_1+M > M$）。
     • 第 $2$ 步：当前 $\max$ 为 $M + S_1$，加到 $a_2$ 上，$a_2$ 变为 $A_2 + M + S_1 = M + S_2$。新 $\max$ 为 $M + S_2$。
     • 依此类推，第 $i$ 步时，当前 $\max$ 为 $M + S_{i-1}$，加到 $a_i$ 上后 $a_i$ 变为 $A_i + M + S_{i-1} = M + S_i$，且 $M + S_i$ 成为新的最大值。
   • 因此操作结束后，每个 $a_i$ 最终值为 $A_i + M + S_{i-1}$。
   • 最终总和：$$f(a) = \sum_{i=1}^{k} (A_i + M + S_{i-1}) = \underbrace{\sum_{i=1}^{k} A_i}_{S_k} + k \cdot M + \underbrace{\sum_{i=0}^{k-1} S_i}_{\text{前缀和的前缀和}}$$
   • 对应 std.cpp 中的三个数组：
     • z[i]：$S_i$，即前 $i$ 个元素的前缀和；
     • x[i]：$M_i = \max(A_1, \dots, A_i)$，即前 $i$ 个元素的最大值；
     • y[i]：$\sum_{j=0}^{i-1} S_j$，即前缀和的前缀和（y[i] = y[i-1] + z[i-1]）。
   • 对于每个 $k$，答案直接由公式 $z[k] + k \cdot x[k] + y[k]$ 计算。

3. 边界与细节：

   • $A_i \ge 1$，保证 $A_i + M > M$，最大值单调递增，归纳成立。
   • 数据范围较大：$N \le 2\times 10^5$，$A_i \le 10^7$。最坏情况下 $S_k \approx 2\times 10^{12}$，$y[k] \approx N \cdot S_k \approx 4\times 10^{17}$，必须使用 long long（C++ 中 64 位有符号整数，上限约 $9\times 10^{18}$），不会溢出。
   • 公式对 $k=1$ 同样成立：$f = A_1 + 1 \cdot A_1 + 0 = 2A_1$，符合预期（唯一元素加自身）。

⏱️ 复杂度分析

• 时间复杂度：$O(N)$。预处理三个前缀数组各需一次线性扫描，回答 $N$ 个询问每次 $O(1)$，总计 $O(N)$。
• 空间复杂度：$O(N)$。需要三个长度为 $N+1$ 的辅助数组 z、x、y。

💻 标准代码 (C++)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
    int n;
    cin>>n;
    // c: 输入数组
    // z[i]: 前 i 个元素的前缀和 S_i（z[0]=0）
    // x[i]: 前 i 个元素的最大值 M_i（x[0]=0）
    // y[i]: 前缀和的前缀和 sum_{j=0}^{i-1} S_j（y[0]=0）
    vector<ll>c(n),z(n+1,0),x(n+1,0),y(n+1,0);
    for(int i=0;i<n;i++)cin>>c[i];
    for(int i=1;i<=n;i++){
        z[i]=z[i-1]+c[i-1];          // 前缀和：S_i = S_{i-1} + A_i
        x[i]=max(x[i-1],c[i-1]);    // 前缀最大值：M_i = max(M_{i-1}, A_i)
        y[i]=y[i-1]+z[i-1];         // 前缀和的前缀和：累加 S_{i-1}
    }
    for(int k=1;k<=n;k++){
        ll m=x[k];                              // 当前前缀的最大值 M
        ll cns=z[k]+1LL*k*m+y[k];               // 公式：S_k + k*M + sum_{i=0}^{k-1} S_i
        cout<<cns<<'\n';
    }
    return 0;
}