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

一个序列的非空连续子序列可以用两个下标I和r(其中0≤l≤r≤n)表示，对应的序列为a_i,a_i+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(n log n).

尝试补全程序

01 #include <iostream>
02 #include <algorithm>
03 #include <vector>04
05 const int MAXN = 100000;
06
07 int n;
08 int a[MAXN];
09 long long ans;
10
11 void solve(int l, int r){
12 if(1+ 1 == r){
13 ans += a[1];
14 return;
15 }
16 int mid =(1+ r)>>1;
17 std::vector<int> pre(a + mid, a +r);
18 for(int i =1; i<r - mid;++i)①;
19 std::vector<long long> sum(r - mid + 1);
20 for(int i =0; i<r -mid;++i)sum[i+1]= sum[i]+pre[i];
21 for(int i = mid - 1,j = mid,max =0; i >=l;--i){
22 while(j<r &&②)++j;
23 max = std::max(max,a[i]);
24 ans +=③;
25 ans +=④;
26 }
27 solve(1,mid);
28 solve(mid,r);
29}
30
31 int main(){32 std::cin >> n;
33 for(int i =0; i<n;++i)std::cin >> a[i];
34 ⑤;
35 std::cout << ans << std::endl;
36 return o;
37}