题解

思路

对长度为 $k$ 的前缀，设原始最大值为 $M_k$。

做法

第一次操作后 $A_1+M_k$ 严格成为新最大值，此后每处理一个位置，刚更新的元素都会成为新最大值，所以最终答案为 $kM_k+kA_1+(k-1)A_2+\cdots+A_k$。令 $S_k=\sum_{i=1}^k A_i$，加权部分也等于 $S_1+S_2+\cdots+S_k$。从左到右同时维护前缀和 $S$、所有前缀和的累加值 $Q$ 和前缀最大值 $M$，第 $k$ 个答案即 $Q+kM$。

复杂度

每个元素只处理一次，时间复杂度为 $O(N)$，空间复杂度为 $O(1)$。