题目题解

问题理解

给定数组 $a$（$0 \le a_i \le n$），可以执行至多一次操作：选择 $i < j$，令 $a_i := a_i + a_j$，$a_j := 0$。
代价为 $j - i$（不操作代价为 $0$）。
定义前缀最小值之和：

对于每个 $x = 0, 1, \dots, n-1$，求在所有代价 $\ge x$ 的操作中 $S$ 的最大值。

第一步：忽略代价，求最大 $S$

先考虑最优操作 $(i, j)$ 应满足什么性质。

观察 1：
如果 $i$ 不是前缀最小值（即存在 $p < i$ 使得 $a_p < a_i$），则增加 $a_i$ 不会改变前缀最小值序列（因为 $a_p$ 仍是更小的前缀最小值），因此操作无意义。
所以 $i$ 必须是前缀最小值。

观察 2：
如果 $j$ 不是后缀最大值（即存在 $q > j$ 使得 $a_q > a_j$），则我们可以选择 $q$ 代替 $j$，因为：

• $a_i + a_q \ge a_i + a_j$，所以 $a_i$ 增加更多（或相等）；
• 设 $a_j$ 为 $0$ 的影响：由于 $a_q > a_j$，将 $a_q$ 置 $0$ 可能使后续前缀最小值更小，但我们可以通过调整 $i$ 的位置来补偿。实际上可以证明，选择更大的 $j$（后缀最大值）不会使答案变差。

因此，我们只需考虑 $i$ 是前缀最小值，$j$ 是后缀最大值。

第二步：枚举候选 $(i, j)$ 对

由于 $a_i \le n$ 且 $i$ 是前缀最小值，这样的 $i$ 最多 $n$ 个。
后缀最大值也最多 $n$ 个。
因此候选对 $(i, j)$ 数量为 $O(n)$（实际上更少，因为 $i < j$ 且 $a_i + a_j$ 不能超过某个上界）。

具体地，对于每个前缀最小值 $i$，我们尝试所有后缀最大值 $j > i$，直到 $a_i + a_j \ge \text{之前的某个前缀最小值}$（因为再增加 $a_i$ 也不会改变前缀最小值序列）。这样每个 $i$ 只需尝试 $O(1)$ 个 $j$。

第三步：计算操作后的 $S$

设我们固定 $(i, j)$，操作后 $a_i' = a_i + a_j$，$a_j' = 0$。

我们需要快速计算新数组的 $S$。
将 $S$ 分解为若干部分：

1. 前缀部分：前 $i-1$ 个元素不受影响，其贡献为 $\text{pref}[i-1]$（已预处理）。
2. 中间部分：从 $i$ 到某个位置 $k-1$，前缀最小值变为 $x = \min(a_i', \text{MN}[i-1])$，其中 $\text{MN}[i-1]$ 是前 $i-1$ 个元素的最小值。
   设 $k$ 是第一个位置 $> i$ 使得 $a_k \le x$（用稀疏表 + 二分查找）。
   则 $i$ 到 $k-1$ 的贡献为 $x \cdot (k - i)$。
3. 剩余部分：从 $k$ 到 $n$，前缀最小值由 $a_k, a_{k+1}, \dots$ 决定。
   我们可以预处理一个“后缀最小值贡献”数组 suffix(k)，表示从 $k$ 开始的 $S$ 值（假设 $k$ 是当前最小）。
   计算 suffix(k) 可用单调栈：找到第一个 $l > k$ 使得 $a_l < a_k$，则$$\text{suffix}(k) = \text{suffix}(l) + a_k \cdot (l - k). $$
4. 减去 $j$ 的影响：由于 $a_j$ 被置 $0$，从 $j$ 开始的前缀最小值可能变小。
   设 $M = \min(\text{前 } i-1 \text{ 的最小值}, x, a_{i+1}, \dots, a_{j-1})$。
   找到第一个 $m \ge j$ 使得 $a_m \le M$，则 $j$ 到 $m-1$ 的贡献原为 $M \cdot (m - j)$，但现在应改为 $0$（因为 $a_j = 0$ 使前缀最小值变为 $0$），因此需要减去这部分。

将以上四部分相加，即得操作后的 $S$。

第四步：处理代价

对于每个候选对 $(i, j)$，其代价为 $d = j - i$，我们得到对应的 $S$ 值。
我们用 best[d] = max(best[d], S) 更新。
最后，从大到小取后缀最大值：best[d] = max(best[d], best[d+1])，因为代价 $\ge d$ 的最大值就是 $\max(best[d], best[d+1], \dots)$。

最终输出 best[0] 到 best[n-1]。

第五步：时间复杂度

• 枚举 $(i, j)$：$O(n)$。
• 每次计算 $S$：$O(\log n)$（二分查找）。
• 总复杂度 $O(n \log n)$，可处理 $n \le 10^6$。

代码实现

#include <bits/stdc++.h>
using namespace std;

const int maxN = 1e6 + 10;
int a[maxN];
long long best[maxN];
long long pref[maxN];
int sec_mn[maxN];
long long pref_sec[maxN];
int MN[maxN];
int f[maxN];

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    for (int i = 0; i <= n - 1; i++) {
        best[i] = 0;
    }
    
    // 后缀最大值
    vector<int> suf_max;
    for (int i = n; i >= 1; i--) {
        if (suf_max.empty() || a[i] > a[suf_max.back()]) {
            suf_max.push_back(i);
        }
    }
    
    // 预处理前缀最小值和次小值
    int mn = 1e9;
    sec_mn[0] = 1e9;
    MN[0] = 1e9;
    int ind = -1;
    for (int i = 1; i <= n; i++) {
        sec_mn[i] = sec_mn[i - 1];
        if (a[i] < mn) {
            if (ind != -1) {
                f[ind] = i;
            }
            sec_mn[i] = mn;
            mn = a[i];
            ind = i;
        } else if (a[i] < sec_mn[i]) {
            sec_mn[i] = a[i];
        }
        MN[i] = mn;
        pref[i] = pref[i - 1] + mn;
        pref_sec[i] = pref_sec[i - 1] + sec_mn[i];
    }
    f[ind] = n + 1;
    
    best[0] = pref[n];
    
    // 单调栈预处理
    vector<int> st{n + 1};
    a[n + 1] = -1e9;
    for (int i = n; i >= 1; i--) {
        if (MN[i - 1] > a[i]) {
            for (int id : suf_max) {
                if (id <= i) break;
                int cur_mn = min(a[i] + a[id], MN[i - 1]);
                // 二分查找第一个 <= cur_mn 的位置
                int l = 0, r = st.size();
                while (r - l > 1) {
                    int mid = (l + r) / 2;
                    if (a[st[mid]] <= cur_mn) l = mid;
                    else r = mid;
                }
                int upto = min(id - 1, st[l] - 1);
                long long val = pref[i - 1] + 1LL * cur_mn * (upto - i + 1);
                if (upto + 1 < id) {
                    int upup = min(f[i], id);
                    val += pref_sec[upup - 1] - pref_sec[upto];
                    val += pref[id - 1] - pref[upup - 1];
                }
                best[id - i] = max(best[id - i], val);
                if (a[i] + a[id] >= MN[i - 1]) break;
            }
        }
        while (!st.empty() && a[i] <= a[st.back()]) st.pop_back();
        st.push_back(i);
    }
    
    // 后缀最大值
    for (int i = n - 2; i >= 0; i--) {
        best[i] = max(best[i], best[i + 1]);
    }
    
    for (int i = 0; i < n; i++) {
        cout << best[i] << " \n"[i == n - 1];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

总结

本题的关键在于：

1. 限制 $i$ 为前缀最小值，$j$ 为后缀最大值，从而将候选对数量降至 $O(n)$。
2. 将 $S$ 分解为若干部分，利用预处理的前缀和、次小值、单调栈等快速计算。
3. 通过后缀最大值得到每个代价 $\ge x$ 的最优答案。