CSP-S 2023 提高级 第一轮（初赛） 完善程序（2）

【题目】

CSP-S 2023 提高级 第一轮（初赛） 完善程序（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)O(nlogn)。

试补全程序。

#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;
}

1.①处应填（）
A. pre[i] = std::max(pre[i - 1], a[i - 1])
B. pre[i + 1] = std::max(pre[i],pre[i + 1])
C. pre[i] = std::max(pre[i -1], a[i])
D. pre[i] = std::max(pre[i], pre[i - 1])
2.②处应填（）
A. a[j] < max
B. a[j] < a[i]
C. pre[j - mid] < max
D. pre[j - mid] > max
3.③处应填（）
A. (long long)(j - mid) * max
B. (long long)(j - mid) * (i - 1) * max
C. sum[j - mid]
D. sum[j - mid] * (i - 1)
4.④处应填（）
A. (long long)(r - j) * max
B. (long long)(r - j) * (mid - i) * max
C. sum[r - mid] - sum[j - mid]
D. (sum[r - mid] - sum[j - mid]) * (mid - i)
5.⑤处应填（）
A. solve(0，n)
B. solve(0，n - 1)
C. solve(1，n)
D. solve(1，n - 1)

【题目考点】

1. 分治算法

2. 区间问题

3. 前缀和

4. vector构造函数

1. vector<T> v(len, val);
   声明vector<T>类型的对象v，初始有len个元素，每个元素的初值为val。如果不填第二个参数val，每个元素的初值为T类型的默认值。整型、浮点型的默认值都为0。
   该构造函数的作用与成员函数v.resize(len, val)的作用相同。
2. vector<T> v(lb, rb);
   声明vector<T>类型的对象v，v中的元素的值是从另一个序列的[lb, rb)（左闭右开区间）拷贝过来的。其中lb是区间下界，rb是区间上界。
   如果原序列是数组，lb、rb类型为该数组类型的指针类型。
   如果原序列是stl容器，lb、rb的类型为容器的迭代器类型。
   该构造函数的作用与成员函数v.assign(len, val)的作用相同。
   例：

int a[10] = {2,4,6,8};
vector<int> v(a, a+4);//v中元素为2，4，6，8

【解题思路】

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);
}

看递归出口，是l+1==r，然后ans变量加的是a[l]。此时看的是长为1的区间，区间中只有a[l]。说明l是区间下界，r是区间上界，[l, r)是左闭右开区间。看最下面的递归调用，将区间[l, r)分为[l, mid)和[mid, r)，分别进行递归调用，这也能说明传入的参数l、r表示的是一个左闭右开区间[l, r)。
整个a数组的下标范围为0到n-1，写成左闭右开区间为[0, n)，因此最初的函数调用为solve(0, n)，第（5）空选A。
函数内，求中点$mid=\frac{l+r}{2}$
pre使用了相当于vector的assign成员函数的构造函数，把a[mid]到a[r-1]复制到了pre序列中。pre[0]的值为a[mid]，pre[1]的值为a[mid+1]，……，pre[r-mid-1]的值为a[r-1]。
for (int i = 1; i < r - mid; ++i) ①;
而后i从1到r-mid-1遍历，看第（1）空的选项可知是要填对pre数组的更新操作。pre数组的意义发生变化。该问题最终要求的是区间最大值的加和，因此此处应该求某一段的最大值，因此表达式中都有max。观察选项，A和C中涉及到了a[i]或a[i-1]，pre的下标i和a的下标i之间存在pre[i] == a[mid+i]这样的关系，而pre[i]和a[i]没有直接关系，表达式中不应该出现a。此处的下标i是从1开始的，而pre数组的下标是从0开始的，如果为pre[i+1]赋值，那么pre[1]的值就没有设。正确的写法是pre[i] = max(pre[i-1], pre[i])，pre[i]更新后的意义为pre[0]~pre[i]的最大值，也就是a数组区间[mid, mid+i]的最大值。第（1）空选D。
设顺序表sum，长度为r-mid+1。

    for (int i = 0; i < r - mid; ++i)sum[i + 1] = sum[i] + pre[i];

这一段很清楚，sum为pre数组的前缀和，sum[i]表示pre数组区间[0, i-1]的加和，即是sum[i+1]表示pre数组区间[0, 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 += ④;}

接下来的循环，i从mid-1循环到l，j从mid循环到r（注意有条件j<r)
对于每次遍历到的a[i]，求最大值max
很明显，现在整个区间[l, r-1]被mid分为两个子区间：[l, mid-1]， [mid, r-1]
两个子区间内部的区间最大值的加和已经通过递归调用统计完成，此时只需要统计左端点在[l, mid-1]范围内，右端点在[mid, r-1]范围内的区间的最大值的加和。
当前循环考虑的就是区间左端点为i，右端点在[mid, r-1]范围内的区间的最大值的加和。
区间最大值有两种情况，最大值在[i, mid-1]范围内，或最大值在[mid, r-1]范围内。

如果第（2）空填a[j] < a[i]，选B。
左端点为i，记区间[i, mid-1]中的最大值为max，值max的下标为im，即max为a[im]。
考虑当i == im，即a[i]是区间[i, mid-1]中的最大值时：

• 如果存在位置jm，满足a[jm]>=a[i]，且区间[mid, j-1]中的元素都小于a[i]，由于循环进行的条件有a[j] < a[i]，那么while循环跳出时，j的值为jm。
• 如果在区间[mid, r]中的元素都小于a[i]，那么j会不断增加直到r，while循环跳出时j为r，可以认为此时jm的值为r。

当i < im时，在之前i为im时j已经增加到jm了，此时j的值为jm。由于a[im]是区间[i, mid-1]中的最大值，所以a[i] <= a[im] <=a[jm]=a[j]，不满足条件a[j] < a[i]，所以while循环跳出。
则以下区间：[i, mid], [i, mid+1], …, [i, j-1]的最大值都为a[im]，即max，区间有j-mid个。因此最大值的加和增加了j-mid个max，即(j-mid)*max，第（3）空选A。
对于左端点为i，右端点大于等于j的区间，设右端点叫做jx，jx满足j<=jx<=r-1。
区间[i, jx]中包括数值a[jm]，由于a[jm]>=a[im]，因此区间[i, jx]的最大值在区间[mid, jx]范围内。
已知pre[i]表示区间[mid, mid+1]中的最大值，那么区间[mid, jx]中的最大值为pre[jx-mid]。
考察最大值在区间[mid, r-1]中的区间，有：
区间[i, j]的最大值为pre[j-mid]
区间[i, j+1]的最大值为pre[j+1-mid]
区间[i, j+2]的最大值为pre[j+2-mid]
…
区间[i, r-1]的最大值为pre[r-1-mid]
求以上各区间最大值的加和，为pre数组区间[j-mid, r-1-mid]的加和。
已知sum[i+1]表示pre数据区间[0, i]的加和。
那么pre数组区间[0, j-mid-1]的加和为sum[j-mid]。
pre数组区间[0, r-1-mid]的加和为sum[r-mid]。
pre数组区间[j-mid, r-1-mid]的加和，为pre数组区间[0, r-1-mid]的加减去pre数组区间[0, j-mid-1]的加和，即sum[r-mid]-sum[j-mid]，因此第（4）空选C。

【答案】

1. D
2. B
3. A
4. C
5. A