(最大值之和)给定整数序列a0,… an-1,求该序列所有非空连续子序列的最大值之和。上述参数满足1≤n≤105和1≤a;≤108。
一个序列的非空连续子序列可以用两个下标l和r(其中0≤l≤r<n)表示，对应的序列为alal+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]和[22]虽然是原序列的子序列，但不是连续子序列，所以不应该被计算。另外，注意其中有一些值相同的子序列，但由于他们在原序列中的下标不同，属于不同的非空连续子序列，所以会被分别计算。解决该问题有许多算法，以下程序使用分治算法，时间复杂度0(nlogn)。
试补全程序。
②处应填()
| A． a[j]< max |
B． a[j]<a[i] |
| C． pre[j-mid]<max |
D． pre[j- mid]> max |
①处应填()
| 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]) |
④处应填()
| A． (long long)(r-j)*max |
B． (long long)(r-j)*(mid -i)*max |
| C． sum[r- mid]- sum[-mid] |
D． (sum[r-mid]- sum[j-mid])*(mid-i) |
③处应填()
| A． (long long)(j -mid)* max |
B． (long long)(j- mid)*(i-1)*max |
| C． sum[j- mid] |
D． sum[j-mid]*(i-1) |
⑤处应填()
| A． solve(0,n) |
B． solve(0, n-1) |
| C． solve(1,n) |
D． solve(1, n-1) |
