E. Explosions?
题目抽象为现有长度为 \(n\) 的数组 \(a_1,a_2,\cdots,a_n\) \((1\le a_i\le 10^{6})\)。
定义满足以下条件的区间 \([l,r]\) \((1\le l,r\le n)\) 为爆炸区间：
\(\exists i\in [l,r]\) 使得 \(a\) 在 \([l,i]\) 严格单调递增，\(a\) 在 \([i,r]\) 严格单调递减。
设定 \([l,r]\) 为爆炸区间，\(i\) 满足 \(a_i=\max\limits_{j=l}^{r}a_j\) 为爆炸点。
每次操作可以选一个 \(a_i\) \((a_i> 0)\) 减 \(1\)，代价为 \(1\)，在任意次操作后满足 \(a_i=0\) \((i\notin [l,r])\)，并且 \([l,r]\) 为爆炸区间，那么可以花费代价 \(\max\limits_{i=l}^{r}a_i\) 将该区间的所有数减为 \(0\)，求将该数组全部清零的最小代价。
那么我们枚举 \(i\) 作为爆炸点，记 \([p,q]\) 为以 \(i\) 作为爆炸点的爆炸区间，求出最大的 \((\sum\limits_{j=p}^{q}a_j)-a_i\)，记为 \(x\)，那么 \((\sum\limits_{j=1}^{n}a_j)-x\) 就是答案。
选择一个数作为爆炸点那么这个数肯定不执行减 \(1\) 操作，将 \(a\) 跑两次单调栈，是一个不严格单调递增栈（单调不递减栈），先正着跑，这样可以跑出 \(i\) 只向左爆炸最多能照成多少伤害，翻转 \(a\) 再跑一次，这样可以跑出 \(i\) 只向右爆炸最多能造成多少伤害。
C++ Code
#include <bits/stdc++.h>
using i64 = long long;
void solve() {
int n;
std::cin >> n;
std::vector<int> a(n);
for (int i = 0; i < n; i++) {
std::cin >> a[i];
}
auto work = [&](auto &a) {
auto b = a;
for (int i = 0; i < n; i++) {
b[i] -= i;
}
std::vector<i64> res(n);
std::vector<int> st;
for (int i = 0; i < n; i++) {
while (!st.empty() && b[st.back()] > b[i]) {
st.pop_back();
}
if (!st.empty() && a[i] - (i - st.back()) >= 0) {
int d = i - st.back();
res[i] = res[st.back()] + 1LL * d * (a[i] + a[i] - d + 1) / 2;
} else {
int d = std::min(i + 1, a[i] + 1);
res[i] = 1LL * d * (a[i] + a[i] - d + 1) / 2;
}
st.push_back(i);
}
return res;
};
auto l = work(a);
reverse(a.begin(), a.end());
auto r = work(a);
reverse(r.begin(), r.end());
reverse(a.begin(), a.end());
i64 ans = 0;
for (int i = 0; i < n; i++) {
ans = std::max(ans, l[i] + r[i] - 2 * a[i]);
}
i64 sum = std::accumulate(a.begin(), a.end(), 0LL);
std::cout << sum - ans << '\n';
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t = 1;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}