2023年信奥赛C++提高组csp-s初赛真题及答案解析（完善程序第2题）
#### 第2题
（最大值之和）给定整数序列a 0 , ⋯ , a n − 1 a_0,⋯,a_{n−1}a0,⋯,an−1，求该序列所有非空连续子序列的最大值之和。上述参数满足1 ≤ n ≤ 10 5 和 1 ≤ a i ≤ 10 8 1≤n≤10^5和 1≤a_i≤10^81≤n≤105和1≤ai≤108。
一个序列的非空连续子序列可以用两个下标 l和 r（其中0≤l≤r<n）表示，对应的序列为a l , a l + 1 , ⋯ , a r a_l,a_{l+1},⋯,a_ral,al+1,⋯,ar。两个非空连续子序列不同，当且仅当下标不同。
例如，当原序列为[ 1 , 2 , 1 , 2 ] [1,2,1,2][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>constintMAXN=100000;intn;inta[MAXN];longlongans;voidsolve(intl,intr){if(l+1==r){ans+=a[l];return;}intmid=(l+r)>>1;std::vector<int>pre(a+mid,a+r);for(inti=1;i<r-mid;++i)①;std::vector<longlong>sum(r-mid+1);for(inti=0;i<r-mid;++i)sum[i+1]=sum[i]+pre[i];for(inti=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);}intmain(){std::cin>>n;for(inti=0;i<n;++i)std::cin>>a[i];⑤;std::cout<<ans<<std::endl;return0;}①处应填（）
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.
a[j] < maxB.
a[j] < a[i]C.
pre[j - mid] < maxD.
pre[j - mid] > max③处应填（）
A.
(long long)(j - mid) * maxB.
(long long)(j - mid) * (i - 1) * maxC.
sum[j - mid]D.
sum[j - mid] * (i - 1)④处应填（）
A.
(long long)(r - j) * maxB.
(long long)(r - j) * (mid - i) * maxC.
sum[r - mid] - sum[j - mid]D.
(sum[r - mid] - sum[j - mid]) * (mid - i)⑤处应填（）
A.
solve(0，n)B.
solve(0，n - 1)C.
solve(1，n)D.
solve(1，n - 1)
解题思路
该程序使用分治算法计算序列所有非空连续子序列的最大值之和。分治的核心思想是将区间[ l , r ) [l, r)[l,r)分成左右两半[ l , mid ) [l, \text{mid})[l,mid)和[ mid , r ) [\text{mid}, r)[mid,r)，递归计算左右内部的贡献，再计算跨越中点的子序列的贡献。
跨越中点贡献的计算：
- 预处理右半部分的前缀最大值数组
pre及其前缀和数组sum。 - 对于每个左端点i ii（从mid − 1 \text{mid}-1mid−1向左枚举），维护左半部分的最大值max \text{max}max，并利用双指针j jj将右端点分为两部分：
- 右端点j ∈ [ mid , j 0 ) j \in [\text{mid}, j_0)j∈[mid,j0)：区间最大值由左半部分贡献，即max \text{max}max。
- 右端点j ∈ [ j 0 , r ) j \in [j_0, r)j∈[j0,r)：区间最大值由右半部分贡献，即pre [ j − mid ] \text{pre}[j-\text{mid}]pre[j−mid]。
- 指针j jj的移动条件为：a [ j ] < a [ i ] a[j] < a[i]a[j]<a[i]，即找到第一个a [ j ] ≥ a [ i ] a[j] \ge a[i]a[j]≥a[i]的位置。
答案及解析
- ①
D：预处理pre为右半部分的前缀最大值。 - ②
B：移动指针j jj的条件为a [ j ] < a [ i ] a[j] < a[i]a[j]<a[i]。 - ③
A：第一组贡献为( j − mid ) × max (\text{j} - \text{mid}) \times \text{max}(j−mid)×max。 - ④
C：第二组贡献为sum [ r − mid ] − sum [ j − mid ] \text{sum}[r-\text{mid}] - \text{sum}[j-\text{mid}]sum[r−mid]−sum[j−mid]。 - ⑤
A：初始调用为solve(0, n)，表示整个区间[ 0 , n ) [0, n)[0,n)。
专栏推荐：信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）
https://blog.csdn.net/weixin_66461496/category_13125089.html
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}1、csp信奥赛高频考点知识详解及案例实践：
CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转
CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转
信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html
2、csp信奥赛冲刺一等奖有效刷题题解：
CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）
https://blog.csdn.net/weixin_66461496/category_13125089.html
3、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html
4、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}
