貌似没有线段树做法。
记\(s\)为\(a\)的前缀和数组。
对于一个确定的右端点 \(r\) 和左端点 \(l\)，它对于答案的贡献是 \(s_r-s_{l-1}-max\{a_i\},l\le i\le r\) ，如果枚举右端点，令 \(c_l=s_{l-1}+max\{a_i\},l\le i\) 。那么其实就是要求 \(1\le k\le r-1\) 的 \(min\{c_k\}\)。
线段树维护 \(c_k\) 即可。
用单调栈求出 \(a_i\) 左边第一个大于自己的数 \(a_p\)，然后把 \([p,i-1]\) 的 \(max\{a_i\}\) 覆盖成 \(a_r\) 即可。
然后你发现要维护 \(c\) ，你得维护 \(s\) 的最小值，和 \(max\{a_i\}\) 。
时间复杂度 \(O(nlogn)\) 。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], n, s[N];
int stk[N], top;
struct Node {
int l, r;
int s, a, v; // s[i] + a[i]
int tag;
}tr[N << 2];
void pushup(int u) {
tr[u].v=min(tr[u<<1].v,tr[u<<1|1].v);
tr[u].s=min(tr[u<<1].s,tr[u<<1|1].s);
}
void pushdown(int u) {
if (tr[u].tag != 2e9) {
tr[u<<1].a=tr[u].tag,tr[u<<1].v=tr[u<<1].s+tr[u].tag;
tr[u<<1|1].a=tr[u].tag,tr[u<<1|1].v=tr[u<<1|1].s+tr[u].tag;
tr[u<<1|1].tag=tr[u<<1].tag=tr[u].tag;
tr[u].tag = 2e9;
}
}
void build(int u,int l,int r) {
tr[u]={l,r};
tr[u].tag=2e9;
if (l==r) {
tr[u].a=1e9;
tr[u].s=s[l];
tr[u].v=tr[u].a+tr[u].s;
tr[u].tag=2e9;
return;
}
int mid = l +r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
void modify(int u,int L,int R,int k) {
if (tr[u].l>=L&&tr[u].r<=R) {
tr[u].a=k;
tr[u].v=tr[u].s+k;
tr[u].tag=k;
return ;
}
int mid=tr[u].l+tr[u].r>>1;
pushdown(u);
if (L<=mid) modify(u<<1,L,R,k);
if (R>mid) modify(u<<1|1,L,R,k);
pushup(u);
}
int query(int u,int L,int R) {
if (tr[u].l>=L&&tr[u].r<=R)
return tr[u].v;
int mid=tr[u].l+tr[u].r>>1;
pushdown(u);
int res=2e9;
if (L<=mid) res=min(res,query(u<<1,L,R));
if (R>mid) res=min(res,query(u<<1|1,L,R));
return res;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i];
int ans = 0;
build(1,0,n);
for (int i = 1; i <= n; i ++ ) {
while (top && a[stk[top]] <= a[i]) top -- ;
// [stk[top], i-1]拍成 a[i]+s[k]
modify(1,stk[top],i-1,a[i]);
ans=max(ans,s[i]-query(1,0,i-1));
stk[ ++ top] = i;
}
cout << ans << endl;
return 0;
}