(最大值之和)给定整数序列ao,a₁,a₂……an,求

第1题

(最大值之和)给定整数序列ao,a₁,a₂……an,求该序列所有非空连续子序列的最大值之和。上述参数满足1≤n≤10⁵和1≤ai≤108。

一个序列的非空连续子序列可以用两个下标I和r(其中0≤l≤r≤n)表示，对应的序列为ai,ai+1,……ar。两个非空连续子序列不同，当且仅当下标不同。

例如，当原序列为[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>04
const int MAXN = 100000;
int n;
int a[MAXN];
long long ans;
void solve(int l, int r){
if(1+ 1 == r){
 ans += a[1];
 return;
}
int mid =(1+ 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(1,mid);
solve(mid,r);
}
int main(){32 std::cin >> n;
for(int i =0; i<n;++i)std::cin >> a[i];
⑤;
 std::cout << ans << std::endl;
 return o;
}

⑤处应填()