80430 - CSP-S2023完善程序2
统计题目(材料题)
（最大值之和）给定整数序列$ a_0,⋯,a_{n−1}，求该序列所有非空连续子序列的最大值之和。上述参数满足 1≤n≤10^5 和 1≤a_i≤10^8 。
一个序列的非空连续子序列可以用两个下标 $l$ 和 $r$（其中$0≤l≤r<n$）表示，对应的序列为 $a_l,a_{l+1},⋯,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(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;
}
||
关注我们
