Edu-CF-184-C. Range Operation（仅有一次的，进行奇奇怪怪操作的，均可以用 dp 解决）（式子中有 r，l，一定要想办法分离） · znzryb
## 题目大意
# CF2169C Range Operation
## 题目描述
给定一个长度为 $n$ 的整数数组 $a$。
你可以进行以下操作：选择一个区间 $[l, r]$（$1 \le l \le r \le n$），并将区间内的元素 $a_l, a_{l+1}, \dots, a_r$ 全部替换为 $l + r$。
你的任务是计算，在最多允许进行一次上述操作的情况下，数组的和可能达到的最大值。
## 输入格式
第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。
每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 2n$）。
输入额外限制：所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。
## 输出格式
对于每个测试用例，输出一个整数，表示在至多进行一次操作后数组的最大和。
## 输入输出样例 #1
### 输入 #1
```
4
3
2 5 1
2
4 4
4
1 3 2 1
5
3 2 0 9 10
```
### 输出 #1
```
13
8
20
32
```
## 说明/提示
在第一个样例中，可以对子数组 $[3,3]$ 执行操作，得到数组 $[2, 5, 6]$，其和为 $13$。
在第二个样例中，不需进行任何操作。
在第三个样例中，可以对子数组 $[1,4]$ 执行操作，得到数组 $[5, 5, 5, 5]$，其和为 $20$。
在第四个样例中，可以对子数组 $[2,3]$ 执行操作，得到数组 $[3, 5, 5, 9, 10]$，其和为 $32$。
由 ChatGPT 5 翻译
## 思路讲解
类似于求解最大字段和的 dp。
思路参考了 starsilk 的代码。
首先，我们必须要把 $r,l$ 两者分开。
我们就会发现，总答案就可以写为：（$S_{x}$ 表示 $x$ 的前缀和）
$$
ans=S_{l-1}+l(1-l)+S_n-S_{r}+r(r+1)
$$
这个明显可以使用这个 dp，因为我们只需要最优化 $S_{l-1}+l(1-l)$ 这个值，就直接最优化了左端点。而右端点的转移，一旦不用考虑这个左端点是不是最优的，就容易多了。
那我们定义，$dp_{i,0}$ 为前缀和（操作前），$dp_{i,1}$ 表示从 $i$ 及之前开始转化的最大化 $S_{l-1}+l(1-l)$ 值（可以理解为操作中，但是不严谨），$dp_{i,2}$ 表示 $i$ 以及之前转化结束，所能达到的最大和（操作后）。
之所以定义三个状态，而不是两个，是为了避免重复操作。
$$
dp_{i,0}=dp_{i-1,0}+a_i\\
dp_{i,1}=\max(dp_{i-1,1},dp_{i-1,0}+i(1-i))\\
dp_{i,2}=\max(dp_{i-1,2}+a_i,dp_{i,1}+i(i+1))
$$
这个状态转移式子中 $dp_{i,2}$ 之所以有两个来源，就是其状态定义，在 $i$ 之前转化结束一个来源，在 $i$ 结束一个来源。
$i$ 定义为这个长整型，**小心溢出**。
```cpp
// dp[i][0] 就是前缀和，dp[i][1]是这个预备变量
for (ll i=1;i<=N;++i) {
dp[i][0]=dp[i-1][0]+A[i];
// dp[i][1] 代表从 i 开始变换，我们能得到的最大值（左端）
// 即 S[i-1]+i*(1-i) 的最大值
dp[i][1]=max(dp[i-1][1],dp[i-1][0]+i*(1-i));
dp[i][2]=max(dp[i-1][2]+A[i],dp[i][1]+i*(i+1));
}
cout<<max(dp[N][0],dp[N][2])<<"\n";
```
## AC代码
AC
[https://codeforces.com/contest/2169/submission/360407408](https://codeforces.com/contest/2169/submission/360407408)
::: 源代码
```cpp
/**
* Problem: C. Range Operation
* Contest: Educational Codeforces Round 184 (Rated for Div. 2)
* Judge: Codeforces
* URL: https://codeforces.com/contest/2169/problem/C
* Created: 2026-01-28 19:45:52
* Author: Gospel_rock
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <iostream>
#include <numeric>
#include <algorithm>
#include <complex>
#include <map>
#include <ranges>
#include <cstring>
#include <string>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT;
/*
*
*/
void Solve() {
ll N;
cin >> N;
vector<ll> A(N+2);
for (int i=1;i<=N;++i) {
cin>>A[i];
}
vector<vector<ll>> dp(N+2,vector<ll>(3));
// (r-l+1)*(r+l)
//
// dp[i][0] 就是前缀和，dp[i][1]是这个预备变量
for (ll i=1;i<=N;++i) {
dp[i][0]=dp[i-1][0]+A[i];
// dp[i][1] 代表从 i 开始变换，我们能得到的最大值（左端）
// 即 S[i-1]+i*(1-i) 的最大值
dp[i][1]=max(dp[i-1][1],dp[i-1][0]+i*(1-i));
dp[i][2]=max(dp[i-1][2]+A[i],dp[i][1]+i*(i+1));
}
cout<<max(dp[N][0],dp[N][2])<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> lT;
while(lT--)
Solve();
return 0;
}
/*
AC
https://codeforces.com/contest/2169/submission/360407408
vector<ll> pre_sum(N+2);
partial_sum(A.begin()+1,A.begin()+N+1,pre_sum.begin()+1);
ll up_pos=1;
for (int i=1;i<=N;++i) {
up_pos=max(up_pos,(ll)i);
for (int j=up_pos;j<=N;++j) {
up_pos=j;
ll len=j-i+1;
ll add=len*(i+j);
if (i==j) {
if (add>A[i]) {
}
}else {
if () {
}
}
}
}
*/
```
:::
## 心路历程（WA，TLE，MLE……）