题目链接#

https://codeforces.com/problemset/problem/2193/C

题目大意#

给定两个长度为 $n$ 的数组 $a$ 和 $b$，以及 $q$ 个区间查询。 你可以对数组 $a$ 执行任意次（包括 $0$ 次）以下两种操作：

1. 选择一个下标 $i$ ($1 \le i < n$)，将 $a_i$ 替换为 $a_{i+1}$（即 $a_i \leftarrow a_{i+1}$，向左传递数值）；
2. 选择一个下标 $i$ ($1 \le i \le n$)，将 $a_i$ 替换为 $b_i$（即 $a_i \leftarrow b_i$，从 $b$ 数组获取数值）。

对于每个查询给定的区间 $[l, r]$，需要在允许任意次操作的前提下，使区间和最大化：

请输出每个查询对应的最大区间和。

注意：

• 操作次数不限；
• 每个查询相互独立（即回答下一个查询时，数组 $a$ 视为恢复初始状态）；
• 数据规模较大，需使用高效算法。

解题思路#

核心性质：$a_i$ 的最大值只能从后面（下标 $\ge i+1$）传递过来，绝不可能从前面（下标 $\le i-1$）获取。

具体步骤：

1. 倒序遍历：从 $a_n$ 开始向前考虑。
2. 状态转移：对于位置 $i$，其最大值来源于当前 $a_i$、对应 $b_i$ 以及后一位 $a_{i+1}$ 的最大值。 $a_i = \max(a_i, \ b_i, \ a_{i+1})$
3. 更新数组：以此类推，得到更新后的 $a$ 数组（即通过若干次操作后能得到的最大值）。
4. 前缀和查询：对新数组计算前缀和，即可快速响应区间查询。

代码实现#

1
#include <bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
const int N=2e5+10;
5
ll a[N], b[N], sum[N];
6
int T, n, q, l, r;
7
void solve(){
8
  memset(a, 0, sizeof a); //一定要清空, 否则在a[n]=max(a[n], max(a[n+1], b[n]))的时候可能会出错,使用上一次的a[n+1]
9
  memset(sum, 0, sizeof sum);
10
  scanf("%d%d", &n, &q);
11
  for(int i=1;i<=n;i++) scanf("%lld", &a[i]);
12
  for(int i=1;i<=n;i++) scanf("%lld", &b[i]);
13
  for(int i=n;i>=1;i--) a[i]=max(a[i], max(a[i+1], b[i]));
14
  for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];
15
  while(q--){
16
    scanf("%d%d", &l, &r);
17
    printf("%lld ", sum[r]-sum[l-1]);
18
    printf("\n");
19
  }
20
}
21
int main(){
22
  scanf("%d", &T);
23
  while(T--) solve();
24
  return 0;
25
}