简单说就是带修的查询区间最大子段和，用线段树维护即可
对于每个区间，我们肯定要记录它的最大子段和\(v\)，但是怎么维护呢？
我们可以记录下从区间左端点开始的最大子段和\(v1\)，从右端点开始的最大子段和\(v2\)以及区间和\(sum\)
那么\(t[p].sum=t[lc].sum+t[rc].sum\)
\(t[p].v1=max(t[lc].v1,t[lc].sum+t[rc].v1)\)
\(t[p].v2=max(t[rc].v 2,t[rc].sum+t[lc].v2)\)
\(t[p].v=max(t[lc].v2+t[rc].v1,t[lc].v,t[rc].v)\)
正确性应该很显然不需要再给出证明了吧
下放代码
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cctype>
#define ll long long
#define gc getchar
#define maxn 50005
using namespace std;
inline ll read(){
ll a=0;int f=0;char p=gc();
while(!isdigit(p)){f|=p=='-';p=gc();}
while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=gc();}
return f?-a:a;
}int n,m;
struct ahaha{
int v,v1,v2,sum;
}t[maxn<<2];
#define lc p<<1
#define rc p<<1|1
inline void pushup(int p){
t[p].sum=t[lc].sum+t[rc].sum;
t[p].v1=max(t[lc].v1,t[lc].sum+t[rc].v1);
t[p].v2=max(t[rc].v2,t[rc].sum+t[lc].v2);
t[p].v=max(t[lc].v2+t[rc].v1,max(t[lc].v,t[rc].v));
}
void build(int p,int l,int r){
if(l==r){t[p].v=t[p].v1=t[p].v2=t[p].sum=read();return;}
int m=l+r>>1;
build(lc,l,m);build(rc,m+1,r);
pushup(p);
}
ahaha query(int p,int l,int r,int L,int R){
if(l>R||r<L)return {-214748,-214748,-214748,-214748};
if(L<=l&&r<=R)return t[p];
int m=l+r>>1;
ahaha l1=query(lc,l,m,L,R),r1=query(rc,m+1,r,L,R),i;
i.sum=l1.sum+r1.sum;
i.v1=max(l1.v1,l1.sum+r1.v1);
i.v2=max(r1.v2,r1.sum+l1.v2);
i.v=max(l1.v2+r1.v1,max(l1.v,r1.v));
return i;
}
inline void solve(){
int x=read(),y=read();
printf("%d\n",query(1,1,n,x,y).v);
}
int main(){
n=read();
build(1,1,n);
m=read();
while(m--)
solve();
return 0;
}