CSP-S 提高级 · CSP 2023 提高级第一轮 第 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

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题核心是处理分治中跨越中点的子数组最大值统计。拿到题先想：左右递归好写，关键是中间那部分怎么 O(n) 算完？利用右侧预处理的前缀最大值和双指针，对每个左侧元素快速确定其作为最大值的右边界，分两段（左侧最大值本身和右侧区间和）累加即可。

最容易栽跟头的地方是 pre 数组的递推逻辑，很多人会写成和 a[i-1] 比较，其实 pre[i] 代表的是从 mid 开始到 i 这一段的最大值，必须和 pre[i-1] 取 max；右侧 while 循环条件也容易搞反，a[j] < a[i] 才是找第一个大于等于 a[i] 的位置；计算贡献时，左侧直接乘个数，右侧要用前缀和相减，千万别又乘又加搞混了。

考点定位： 这道题考查分治算法在「求所有连续子数组最大值之和」这一变种问题上的应用，核心在于如何高效计算跨越中点的贡献。这类题目在 CSP 提高级中属于经典题型，要求学生在 O(n log n) 时间内完成处理。

分治框架与递归边界： 程序采用标准的分治策略：将区间 [l, r) 从中点 mid 分为左右两半，分别递归求解，最后统计跨越中点的子数组贡献。注意这里的区间是左闭右开 [l, r)，这是 C++ 处理数组区间的习惯写法。递归的终止条件是区间长度为 1（即 l + 1 == r），此时只有一个元素 a[l]，它自己就是最大值，直接加到 ans 中。

预处理右侧前缀最大值（空①）： 为了高效处理跨越中点的子数组，我们需要知道从 mid 开始向右延伸时，最大值是如何变化的。程序定义了一个向量 pre，存储的是从 mid 到 r-1 这一段的前缀最大值。注意 pre 的下标是从 0 开始的，pre[0] 对应原数组的 a[mid]。

代码中 std::vector<int> pre(a + mid, a + r); 初始化了 pre 数组，此时 pre[i] 还是原数组的值。接下来的循环 for (int i = 1; i < r - mid; ++i) 负责递推。这里有一个经典的陷阱：pre[i] 应该取 pre[i-1] 和当前元素 a[i] 的最大值，而不是和 a[i-1] 比较。因为 pre[i-1] 已经是前 i-1 个元素的最大值了，再和 a[i] 比较就能得到前 i 个元素的最大值。所以空①必须选 D：pre[i] = std::max(pre[i], pre[i - 1])。如果选成和 a[i-1] 比较，逻辑就完全错了，因为 pre[i-1] 可能已经比 a[i-1] 大得多了。

双指针寻找右边界（空②）： 接下来是对左侧元素 a[i]（i 从 mid-1 递减到 l）进行处理。对于每一个 a[i]，我们要找到它作为最大值的右边界。显然，从 mid 开始向右，只要遇到比 a[i] 大的元素，a[i] 就不再是最大值了。因此我们需要找到第一个满足 a[j] >= a[i] 的位置 j。

程序使用了双指针技巧：j 初始指向 mid，随着 i 减小，j 只会向右移动（单调性）。while 循环的条件就是寻找这个分界点。空②处填的条件必须是 a[j] < a[i]，表示只要当前位置 j 的值还小于 a[i]，就可以继续向右扩展，直到遇到第一个大于等于 a[i] 的元素为止。所以空②选 B。

计算左侧贡献（空③）： 当找到第一个 a[j] >= a[i] 的位置 j 后，区间 [mid, j) 内的所有元素都小于 a[i]。这意味着所有左端点为 i、右端点在 [mid, j-1] 之间的子数组，其最大值都是 a[i]。这样的子数组个数正好是 j - mid 个。因此，这部分对答案的贡献是 (long long)(j - mid) * max。空③选 A。

计算右侧贡献（空④）： 对于右端点从 j 到 r-1 的子数组，它们的最大值不再是 a[i]，而是由 pre 数组决定。具体来说，区间 [j, r) 内的最大值之和，就是 pre 数组从下标 j - mid 到 r - mid - 1 的和。利用之前预处理好的前缀和数组 sum，这个区间和可以直接用 sum[r - mid] - sum[j - mid] 得到。注意 sum 数组的定义是 sum[k] 表示 pre 前 k 个元素的和（即 pre[0] 到 pre[k-1]），所以区间 [j-mid, r-mid) 的和就是 sum[r-mid] - sum[j-mid]。空④选 C。

主函数入口（空⑤）： 最后看递归调用。题目要求处理整个数组 [0, n)，所以初始调用应该是 solve(0, n)。如果写成 solve(0, n-1)，就会漏掉最后一个元素。空⑤选 A。

总结与避坑： 做这类完善程序题，关键是要理解算法的每一步在做什么。pre 数组的递推是基础，一定要记住是 pre 和 pre 比较；双指针的终止条件要看清是找「第一个大于等于」还是「第一个大于」；贡献计算要分清是纯个数乘法还是前缀和相减。只有把这些细节抠准了，才能避免掉进命题人设下的一个个小坑里。