全部知识点
2023年CSP-S1阅读程序题2：
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
long long solve1(int n){
vector<bool> p(n+1, true);
vector<long long> f(n+1,0),g(n+1,0);
f[1]= 1;
for (int i = 2; i*i <= n; i++){
if (p[i]){
vector<int> d;
for(int k = i;k <=n; k *= i)d.push_back(k);
reverse(d.begin(),d.end());
for (int k:d){for (int j =k; j<=n;j += k){
if (p[j]){
p[j]= false;
f[j]= i;
g[j]= k;
}
}
}
}
}
for (int i = sqrt(n)+ 1; i <= n; i++){
if (p[i]){
f[i]= i;
g[i]= i;
}
}
long long sum = 1;
for(int i = 2; i <= n; i++){
f[i]= f[i / g[i]]*(g[i]* f[i]- 1)/(f[i]- 1);
sum += f[i];
}
return sum;
}
long long solve2(int n){
long long sum = 0;
for(int i= 1; i <= n; i++){
sum += i*(n / i);
}
return sum;
}
int main(){
int n;
cin >> n;
cout << solve1(n)<< endl;
cout << solve2(n)<< endl;
return 0;
}假设输入的n是不超过1000000的自然数，完成下面的判断题和单选题：
当输入为“10”时，输出的第一行大于第二行。（）
2023年CSP-S1阅读程序题2：
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
long long solve1(int n){
vector<bool> p(n+1, true);
vector<long long> f(n+1,0),g(n+1,0);
f[1]= 1;
for (int i = 2; i*i <= n; i++){
if (p[i]){
vector<int> d;
for(int k = i;k <=n; k *= i)d.push_back(k);
reverse(d.begin(),d.end());
for (int k:d){for (int j =k; j<=n;j += k){
if (p[j]){
p[j]= false;
f[j]= i;
g[j]= k;
}
}
}
}
}
for (int i = sqrt(n)+ 1; i <= n; i++){
if (p[i]){
f[i]= i;
g[i]= i;
}
}
long long sum = 1;
for(int i = 2; i <= n; i++){
f[i]= f[i / g[i]]*(g[i]* f[i]- 1)/(f[i]- 1);
sum += f[i];
}
return sum;
}
long long solve2(int n){
long long sum = 0;
for(int i= 1; i <= n; i++){
sum += i*(n / i);
}
return sum;
}
int main(){
int n;
cin >> n;
cout << solve1(n)<< endl;
cout << solve2(n)<< endl;
return 0;
}假设输入的n是不超过1000000的自然数，完成下面的判断题和单选题：
当输入为“1000”时，输出的第一行与第二行相等。（）
2023年CSP-S1阅读程序题2：
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
long long solve1(int n){
vector<bool> p(n+1, true);
vector<long long> f(n+1,0),g(n+1,0);
f[1]= 1;
for (int i = 2; i*i <= n; i++){
if (p[i]){
vector<int> d;
for(int k = i;k <=n; k *= i)d.push_back(k);
reverse(d.begin(),d.end());
for (int k:d){for (int j =k; j<=n;j += k){
if (p[j]){
p[j]= false;
f[j]= i;
g[j]= k;
}
}
}
}
}
for (int i = sqrt(n)+ 1; i <= n; i++){
if (p[i]){
f[i]= i;
g[i]= i;
}
}
long long sum = 1;
for(int i = 2; i <= n; i++){
f[i]= f[i / g[i]]*(g[i]* f[i]- 1)/(f[i]- 1);
sum += f[i];
}
return sum;
}
long long solve2(int n){
long long sum = 0;
for(int i= 1; i <= n; i++){
sum += i*(n / i);
}
return sum;
}
int main(){
int n;
cin >> n;
cout << solve1(n)<< endl;
cout << solve2(n)<< endl;
return 0;
}假设输入的n是不超过1000000的自然数，完成下面的判断题和单选题：
solve1(n)的时间复杂度为(）。
2023年CSP-S1阅读程序题2：
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
long long solve1(int n){
vector<bool> p(n+1, true);
vector<long long> f(n+1,0),g(n+1,0);
f[1]= 1;
for (int i = 2; i*i <= n; i++){
if (p[i]){
vector<int> d;
for(int k = i;k <=n; k *= i)d.push_back(k);
reverse(d.begin(),d.end());
for (int k:d){for (int j =k; j<=n;j += k){
if (p[j]){
p[j]= false;
f[j]= i;
g[j]= k;
}
}
}
}
}
for (int i = sqrt(n)+ 1; i <= n; i++){
if (p[i]){
f[i]= i;
g[i]= i;
}
}
long long sum = 1;
for(int i = 2; i <= n; i++){
f[i]= f[i / g[i]]*(g[i]* f[i]- 1)/(f[i]- 1);
sum += f[i];
}
return sum;
}
long long solve2(int n){
long long sum = 0;
for(int i= 1; i <= n; i++){
sum += i*(n / i);
}
return sum;
}
int main(){
int n;
cin >> n;
cout << solve1(n)<< endl;
cout << solve2(n)<< endl;
return 0;
}假设输入的n是不超过1000000的自然数，完成下面的判断题和单选题：
solve(2)的时间复杂度为（）。
2023年CSP-S1阅读程序题2：
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
long long solve1(int n){
vector<bool> p(n+1, true);
vector<long long> f(n+1,0),g(n+1,0);
f[1]= 1;
for (int i = 2; i*i <= n; i++){
if (p[i]){
vector<int> d;
for(int k = i;k <=n; k *= i)d.push_back(k);
reverse(d.begin(),d.end());
for (int k:d){for (int j =k; j<=n;j += k){
if (p[j]){
p[j]= false;
f[j]= i;
g[j]= k;
}
}
}
}
}
for (int i = sqrt(n)+ 1; i <= n; i++){
if (p[i]){
f[i]= i;
g[i]= i;
}
}
long long sum = 1;
for(int i = 2; i <= n; i++){
f[i]= f[i / g[i]]*(g[i]* f[i]- 1)/(f[i]- 1);
sum += f[i];
}
return sum;
}
long long solve2(int n){
long long sum = 0;
for(int i= 1; i <= n; i++){
sum += i*(n / i);
}
return sum;
}
int main(){
int n;
cin >> n;
cout << solve1(n)<< endl;
cout << solve2(n)<< endl;
return 0;
}假设输入的n是不超过1000000的自然数，完成下面的判断题和单选题：
输入为“5”时，输出的第二行为（）。
2023年CSP-S1阅读程序题3：
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool fo(vector<int>& a, int m, int k){
int s =0;
for(int i =0,j =0; i<a.size(); i++){
while (a[i]- a[j]>m)j++;
s += i -j;
}
return s >= k;
}
int f(vector<int>& a, int k){
sort(a.begin(), a.end());1
int g =0;
int h = a.back()- a[0];
while(g< h){
int m = g+(h -g)/ 2;
if(fo(a,m, k)){
h = m;
} else {
g = m+1;27 }28 }29
return g;31}32
int main(){34 int n,k;35 cin >> n >> k;36 vector<int> a(n,0);37 for(int i =o; i<n; i++){
cin >> a[i];
}
cout<< f(a,k)<< endl;
return 0
}假设输入总是合法的且|a[i]l≤108、n≤10000和1≤k≤n(n-1)/2,完成下面的判断题和单选题：
将第24行的“m”改为“m-1”输出有可能不变，而剩下情况为少1。（）
2023年CSP-S1阅读程序题3：
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool fo(vector<int>& a, int m, int k){
int s =0;
for(int i =0,j =0; i<a.size(); i++){
while (a[i]- a[j]>m)j++;
s += i -j;
}
return s >= k;
}
int f(vector<int>& a, int k){
sort(a.begin(), a.end());1
int g =0;
int h = a.back()- a[0];
while(g< h){
int m = g+(h -g)/ 2;
if(fo(a,m, k)){
h = m;
} else {
g = m+1;27 }28 }29
return g;31}32
int main(){34 int n,k;35 cin >> n >> k;36 vector<int> a(n,0);37 for(int i =o; i<n; i++){
cin >> a[i];
}
cout<< f(a,k)<< endl;
return 0
}假设输入总是合法的且|a[i]l≤108、n≤10000和1≤k≤n(n-1)/2,完成下面的判断题和单选题：
将第22行的“g+(h-g)/2”改为“(h+g)>>1”，输出不变。（）
2023年CSP-S1阅读程序题3：
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool fo(vector<int>& a, int m, int k){
int s =0;
for(int i =0,j =0; i<a.size(); i++){
while (a[i]- a[j]>m)j++;
s += i -j;
}
return s >= k;
}
int f(vector<int>& a, int k){
sort(a.begin(), a.end());1
int g =0;
int h = a.back()- a[0];
while(g< h){
int m = g+(h -g)/ 2;
if(fo(a,m, k)){
h = m;
} else {
g = m+1;27 }28 }29
return g;31}32
int main(){34 int n,k;35 cin >> n >> k;36 vector<int> a(n,0);37 for(int i =o; i<n; i++){
cin >> a[i];
}
cout<< f(a,k)<< endl;
return 0
}假设输入总是合法的且|a[i]l≤108、n≤10000和1≤k≤n(n-1)/2,完成下面的判断题和单选题：
当输入为“572-451-3”，输出为“5”。（）
2023年CSP-S1阅读程序题3：
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool fo(vector<int>& a, int m, int k){
int s =0;
for(int i =0,j =0; i<a.size(); i++){
while (a[i]- a[j]>m)j++;
s += i -j;
}
return s >= k;
}
int f(vector<int>& a, int k){
sort(a.begin(), a.end());1
int g =0;
int h = a.back()- a[0];
while(g< h){
int m = g+(h -g)/ 2;
if(fo(a,m, k)){
h = m;
} else {
g = m+1;27 }28 }29
return g;31}32
int main(){34 int n,k;35 cin >> n >> k;36 vector<int> a(n,0);37 for(int i =o; i<n; i++){
cin >> a[i];
}
cout<< f(a,k)<< endl;
return 0
}假设输入总是合法的且|a[i]l≤108、n≤10000和1≤k≤n(n-1)/2,完成下面的判断题和单选题：
设a数组中最大值减最小值加1为A，则f函数的时间复杂度为（）。
2023年CSP-S1阅读程序题3：
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool fo(vector<int>& a, int m, int k){
int s =0;
for(int i =0,j =0; i<a.size(); i++){
while (a[i]- a[j]>m)j++;
s += i -j;
}
return s >= k;
}
int f(vector<int>& a, int k){
sort(a.begin(), a.end());1
int g =0;
int h = a.back()- a[0];
while(g< h){
int m = g+(h -g)/ 2;
if(fo(a,m, k)){
h = m;
} else {
g = m+1;27 }28 }29
return g;31}32
int main(){34 int n,k;35 cin >> n >> k;36 vector<int> a(n,0);37 for(int i =o; i<n; i++){
cin >> a[i];
}
cout<< f(a,k)<< endl;
return 0
}假设输入总是合法的且|a[i]l≤108、n≤10000和1≤k≤n(n-1)/2,完成下面的判断题和单选题：
将第10行中的“>”替换为“>=”，那么原输出与现输出的大小关系为（）。
2023年CSP-S1阅读程序题3：
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool fo(vector<int>& a, int m, int k){
int s =0;
for(int i =0,j =0; i<a.size(); i++){
while (a[i]- a[j]>m)j++;
s += i -j;
}
return s >= k;
}
int f(vector<int>& a, int k){
sort(a.begin(), a.end());1
int g =0;
int h = a.back()- a[0];
while(g< h){
int m = g+(h -g)/ 2;
if(fo(a,m, k)){
h = m;
} else {
g = m+1;27 }28 }29
return g;31}32
int main(){34 int n,k;35 cin >> n >> k;36 vector<int> a(n,0);37 for(int i =o; i<n; i++){
cin >> a[i];
}
cout<< f(a,k)<< endl;
return 0
}假设输入总是合法的且|a[i]l≤108、n≤10000和1≤k≤n(n-1)/2,完成下面的判断题和单选题：
当输入为“582-538-12”时，输出为（）。
(第k小路径)给定一张.个点.条边的有向无环图，顶点编号从0到n-1。对于一条路径，我们定义"路径序列"为该路径从起点出发依次经过的顶点编号构成的序列。求所有至少包含一个点的简单路径中，“路径序列"字典序第k小的路径。保证存在至少k条路径。上述参数满足1≤n.m≤105和1≤k≤1018。
在程序中，我们求出从每个点出发的路径数量。超过1018的数都用1018表示。然后我们根据k的值和每个顶点的路径数量，确定路径的起点，然后可以类似地依次求出路径中的每个点。
试补全程序。
#include <iostream>
#include <algorithm>
#include <vector>
const int MAXN = 100000;
constlonglongLIM=100000000000000000011;
int n,m,deg[MAXN];
std::vector<int> E[MAXN];
long long k,f[MAXN];
int
next(std::vector<int>cand,long long
&k){
std::sort(cand.begin(),cand.end());
for(int u : cand){
if (①)return u;
k -= f[u];
}
return -1;
}
int main(){
std::cin>>n>>m>>k;
for(inti=0;i<m;++i){
int u, v;
std::cin >>u >> v;//一条从u到v的边
E[u].push_back(v);
++deg[v];
}
std::vector<int> Q;
for(inti=0;i<n;++i)
if (!deg[i])Q.push_back(i);
for(inti=0;i<n;++i){
int u = Q[i];
for (int v : E[u]){
if (②)Q.push_back(v);
--deg[v];
}
}
std::reverse(Q.begin(), Q.end());
for(int u : Q){
f[u]= 1;
for(int v:E[u])f[u]=③;
}
int u = next(Q,k);
std::cout << u << std::endl;
while(④){
⑤;
u = next(E[u],k);
std::cout << u << std::endl;
}
return 0;
}①处应填( )
(第k小路径)给定一张.个点.条边的有向无环图，顶点编号从0到n-1。对于一条路径，我们定义"路径序列"为该路径从起点出发依次经过的顶点编号构成的序列。求所有至少包含一个点的简单路径中，“路径序列"字典序第k小的路径。保证存在至少k条路径。上述参数满足1≤n.m≤105和1≤k≤1018。
在程序中，我们求出从每个点出发的路径数量。超过1018的数都用1018表示。然后我们根据k的值和每个顶点的路径数量，确定路径的起点，然后可以类似地依次求出路径中的每个点。
试补全程序。
#include <iostream>
#include <algorithm>
#include <vector>
const int MAXN = 100000;
constlonglongLIM=100000000000000000011;
int n,m,deg[MAXN];
std::vector<int> E[MAXN];
long long k,f[MAXN];
int
next(std::vector<int>cand,long long
&k){
std::sort(cand.begin(),cand.end());
for(int u : cand){
if (①)return u;
k -= f[u];
}
return -1;
}
int main(){
std::cin>>n>>m>>k;
for(inti=0;i<m;++i){
int u, v;
std::cin >>u >> v;//一条从u到v的边
E[u].push_back(v);
++deg[v];
}
std::vector<int> Q;
for(inti=0;i<n;++i)
if (!deg[i])Q.push_back(i);
for(inti=0;i<n;++i){
int u = Q[i];
for (int v : E[u]){
if (②)Q.push_back(v);
--deg[v];
}
}
std::reverse(Q.begin(), Q.end());
for(int u : Q){
f[u]= 1;
for(int v:E[u])f[u]=③;
}
int u = next(Q,k);
std::cout << u << std::endl;
while(④){
⑤;
u = next(E[u],k);
std::cout << u << std::endl;
}
return 0;
}②处应填( )
(第k小路径)给定一张.个点.条边的有向无环图，顶点编号从0到n-1。对于一条路径，我们定义"路径序列"为该路径从起点出发依次经过的顶点编号构成的序列。求所有至少包含一个点的简单路径中，“路径序列"字典序第k小的路径。保证存在至少k条路径。上述参数满足1≤n.m≤105和1≤k≤1018。
在程序中，我们求出从每个点出发的路径数量。超过1018的数都用1018表示。然后我们根据k的值和每个顶点的路径数量，确定路径的起点，然后可以类似地依次求出路径中的每个点。
试补全程序。
#include <iostream>
#include <algorithm>
#include <vector>
const int MAXN = 100000;
constlonglongLIM=100000000000000000011;
int n,m,deg[MAXN];
std::vector<int> E[MAXN];
long long k,f[MAXN];
int
next(std::vector<int>cand,long long
&k){
std::sort(cand.begin(),cand.end());
for(int u : cand){
if (①)return u;
k -= f[u];
}
return -1;
}
int main(){
std::cin>>n>>m>>k;
for(inti=0;i<m;++i){
int u, v;
std::cin >>u >> v;//一条从u到v的边
E[u].push_back(v);
++deg[v];
}
std::vector<int> Q;
for(inti=0;i<n;++i)
if (!deg[i])Q.push_back(i);
for(inti=0;i<n;++i){
int u = Q[i];
for (int v : E[u]){
if (②)Q.push_back(v);
--deg[v];
}
}
std::reverse(Q.begin(), Q.end());
for(int u : Q){
f[u]= 1;
for(int v:E[u])f[u]=③;
}
int u = next(Q,k);
std::cout << u << std::endl;
while(④){
⑤;
u = next(E[u],k);
std::cout << u << std::endl;
}
return 0;
}③处应填( )
(第k小路径)给定一张.个点.条边的有向无环图，顶点编号从0到n-1。对于一条路径，我们定义"路径序列"为该路径从起点出发依次经过的顶点编号构成的序列。求所有至少包含一个点的简单路径中，“路径序列"字典序第k小的路径。保证存在至少k条路径。上述参数满足1≤n.m≤105和1≤k≤1018。
在程序中，我们求出从每个点出发的路径数量。超过1018的数都用1018表示。然后我们根据k的值和每个顶点的路径数量，确定路径的起点，然后可以类似地依次求出路径中的每个点。
试补全程序。
#include <iostream>
#include <algorithm>
#include <vector>
const int MAXN = 100000;
constlonglongLIM=100000000000000000011;
int n,m,deg[MAXN];
std::vector<int> E[MAXN];
long long k,f[MAXN];
int
next(std::vector<int>cand,long long
&k){
std::sort(cand.begin(),cand.end());
for(int u : cand){
if (①)return u;
k -= f[u];
}
return -1;
}
int main(){
std::cin>>n>>m>>k;
for(inti=0;i<m;++i){
int u, v;
std::cin >>u >> v;//一条从u到v的边
E[u].push_back(v);
++deg[v];
}
std::vector<int> Q;
for(inti=0;i<n;++i)
if (!deg[i])Q.push_back(i);
for(inti=0;i<n;++i){
int u = Q[i];
for (int v : E[u]){
if (②)Q.push_back(v);
--deg[v];
}
}
std::reverse(Q.begin(), Q.end());
for(int u : Q){
f[u]= 1;
for(int v:E[u])f[u]=③;
}
int u = next(Q,k);
std::cout << u << std::endl;
while(④){
⑤;
u = next(E[u],k);
std::cout << u << std::endl;
}
return 0;
}④处应填( )
(第k小路径)给定一张.个点.条边的有向无环图，顶点编号从0到n-1。对于一条路径，我们定义"路径序列"为该路径从起点出发依次经过的顶点编号构成的序列。求所有至少包含一个点的简单路径中，“路径序列"字典序第k小的路径。保证存在至少k条路径。上述参数满足1≤n.m≤105和1≤k≤1018。
在程序中，我们求出从每个点出发的路径数量。超过1018的数都用1018表示。然后我们根据k的值和每个顶点的路径数量，确定路径的起点，然后可以类似地依次求出路径中的每个点。
试补全程序。
#include <iostream>
#include <algorithm>
#include <vector>
const int MAXN = 100000;
constlonglongLIM=100000000000000000011;
int n,m,deg[MAXN];
std::vector<int> E[MAXN];
long long k,f[MAXN];
int
next(std::vector<int>cand,long long
&k){
std::sort(cand.begin(),cand.end());
for(int u : cand){
if (①)return u;
k -= f[u];
}
return -1;
}
int main(){
std::cin>>n>>m>>k;
for(inti=0;i<m;++i){
int u, v;
std::cin >>u >> v;//一条从u到v的边
E[u].push_back(v);
++deg[v];
}
std::vector<int> Q;
for(inti=0;i<n;++i)
if (!deg[i])Q.push_back(i);
for(inti=0;i<n;++i){
int u = Q[i];
for (int v : E[u]){
if (②)Q.push_back(v);
--deg[v];
}
}
std::reverse(Q.begin(), Q.end());
for(int u : Q){
f[u]= 1;
for(int v:E[u])f[u]=③;
}
int u = next(Q,k);
std::cout << u << std::endl;
while(④){
⑤;
u = next(E[u],k);
std::cout << u << std::endl;
}
return 0;
}⑤处应填( )
(最大值之和)给定整数序列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;
}①处应填（）
(最大值之和)给定整数序列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;
}②处应填（）
(最大值之和)给定整数序列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;
}③处应填()
(最大值之和)给定整数序列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;
}④处应填()
