CSP-S 2023 第一轮 第40题：完善程序（第 20 题）第 2 空

题目

（最大值之和）给定整数序列 $a_0,\cdots,a_{n-1}$，求该序列所有非空连续子序列的最大值之和。上述参数满足 $1\le n\le 10^5$ 和 $1\le a_i\le 10^8$。

一个序列的非空连续子序列可以用两个下标 $l$ 和 $r$（其中$0 \le l \le r < n$）表示，对应的序列为 $a_l,a_{l+1},\cdots,a_r$。两个非空连续子序列不同，当且仅当下标不同。

例如，当原序列为 $[1,2,1,2]$ 时，要计算子序列 $[1]$、$[2]$、$[1]$、$[2]$、$[1,2]$、$[2,1]$、$[1,2]$、$[1,2,1]$、$[2,1,2]$、$[1,2,1,2]$ 的最大值之和，答案为 $18$。注意 $[1,1]$ 和 $[2,2]$ 虽然是原序列的子序列，但不是连续子序列，所以不应该被计算。另外，注意其中有一些值相同的子序列，但由于他们在原序列中的下标不同，属于不同的非空连续子序列，所以会被分别计算。

解决该问题有许多算法，以下程序使用分治算法，时间复杂度 $O(n\log n)$。

试补全程序。

#include <iostream>
#include <algorithm>
#include <vector>

const int MAXN = 100000;

int n;
int a[MAXN];
long long ans;

void solve(int l, int r) {
    if (l + 1 == r) {
        ans += a[l];
        return;
    }
    int mid = (l + r) >> 1;
    std::vector<int> pre(a + mid, a + r);
    for (int i = 1; i < r - mid; ++i) ①;
    std::vector<long long> sum(r - mid + 1);
    for (int i = 0; i < r - mid; ++i)
        sum[i + 1] = sum[i] + pre[i];
    for (int i = mid - 1, j = mid, max = 0; i >= l; --i) {
        while (j < r && ②) ++j;
        max = std::max(max, a[i]);
        ans += ③;
        ans += ④;
    }
    solve(l, mid);
    solve(mid, r);
}

int main() {
    std::cin >> n;
    for (int i = 0; i < n; ++i)
        std::cin >> a[i];
    ⑤;
    std::cout << ans << std::endl;
    return 0;
}

②处应填（）

选项

• A. a[j] < max
• B. a[j] < a[i]
• C. pre[j - mid] < max
• D. pre[j - mid] > max

答案

B

题解

答案选 B：a[j] < a[i]。

这里的分治区间是左闭右开区间 [l,r)。循环负责统计跨过 mid 的连续子序列：固定左端点 i，右端点可以取 mid 到 r-1。

其中：

• max 更新后表示左半部分 a[i..mid-1] 的最大值。
• j 表示右半部分中，第一个大于等于这个最大值的位置；不存在时，j=r。

关键是下面两句的执行顺序：

``cpp while (j < r && a[j] < a[i]) ++j; max = std::max(max, a[i]); ``

执行 while 时，max 还没包含当前的 a[i]，所以不能直接用选项 A 或 C。

为什么只和 a[i] 比较就够了？因为 i 从右往左移动，j 保留上一次的位置：

1. 如果 a[i] <= max，左侧最大值不变。原来的 a[j] >= max >= a[i]，所以 j 不动。
2. 如果 a[i] > max，左侧最大值将变为 a[i]，就继续跳过右侧所有小于 a[i] 的元素。

这样，更新 max 后，跨中点的区间可以分成两类：

因此后面的两项贡献对应：

``cpp ans += 1LL * (j - mid) * max; ans += sum[r - mid] - sum[j - mid]; ``

这道题的关键：while 在更新 max 之前执行，要用新加入的 a[i] 推进指针。