CF2124G.Maximise Sum

本题与 B 题不同。在本题中，对于每个整数 $x$，$0 \le x \le n-1$，你需要输出所有操作代价至少为 $x$ 时，前缀最小值之和的最大值。

给定一个长度为 $n$ 的数组 $a$，其中 $0 \le a_i \le n$。你最多可以进行一次如下操作：

• 选择两个下标 $i$ 和 $j$，满足 $i < j$。将 $a_i := a_i + a_j$，然后将 $a_j = 0$。

一次操作的代价为 $j-i$。如果不进行操作，则代价为 $0$。

对于每个整数 $x$，$0 \le x \le n-1$，输出所有操作代价至少为 $x$ 时，$\min(a_1) + \min(a_1,a_2) + \ldots + \min(a_1, a_2, \ldots, a_n)$ 的最大可能值。

每组测试数据包含多组测试用例。第一行包含整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$2 \leq n \leq 10^6$），表示数组 $a$ 的长度。

接下来一行包含 $n$ 个用空格分隔的整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le n$），表示数组 $a$。

保证所有测试用例中 $n$ 的总和不超过 $10^6$。

对于每个测试用例，输出 $n$ 个整数，表示对于每个 $i$，所有操作代价至少为 $i-1$ 时的最大答案。每个测试用例输出一行，数之间用空格分隔。

我们来分析第五个测试用例：

• $x=0,1,2$：最优操作是 $i=2$，$j=4$，代价为 $2$。此时数组 $a$ 变为 $[4,4,3,0,1]$，得分为 $11$。
• $x=3$：最优操作是 $i=2$，$j=5$，代价为 $3$。此时数组 $a$ 变为 $[4,2,3,3,0]$，得分为 $10$。
• $x=4$：最优（且唯一）操作是 $i=1$，$j=5$，代价为 $4$。此时数组 $a$ 变为 $[5,1,3,3,0]$，得分为 $8$。

由 ChatGPT 4.1 翻译