代码如下:
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#define MAXN 10005
#define lson(o) (o<<1)//左儿子
#define rson(o) (o<<1|1)//右儿子
using namespace std;
int a[MAXN],n,m;
struct Node{
int p,l,r,sum;
//p:区间最大子段和
//l:区间最大前缀和
//r:区间最大后缀和
//sum:区间和
Node(int _p,int _l,int _r,int _s)
:p(_p),l(_l),r(_r),sum(_s){}
Node(){}
};
struct SMT{
Node d[MAXN<<2];
inline void pushup(int o){
d[o].p=max(max(d[lson(o)].p,d[rson(o)].p),d[lson(o)].r+d[rson(o)].l);
d[o].l=max(d[lson(o)].l,d[rson(o)].l+d[lson(o)].sum);
d[o].r=max(d[rson(o)].r,d[lson(o)].r+d[rson(o)].r);
d[o].sum=d[lson(o)].sum+d[rson(o)].sum;
}//区间最大子段和常见套路,维护最大前缀/后缀/子段和,区间和。
inline void build(int l,int r,int o){
if(l==r){
d[o]=Node(a[l],a[l],a[l],a[l]);
return ;
}
int mid=(l+r)>>1;
build(l,mid,lson(o));
build(mid+1,r,rson(o));
pushup(o);
}//建树
inline Node Q(int l,int r,int ql,int qr,int o){
if(l>r){
Node t=Node(0,0,0,0);
return t;
}
if(l<=ql&&qr<=r){
return d[o];
}
int mid=(ql+qr)>>1;
if(l<=mid)return Q(l,r,ql,mid,lson(o));
if(r>mid)return Q(l,r,mid+1,qr,rson(o));
Node tmp,t1=Q(l,r,ql,mid,lson(o)),t2=Q(l,r,mid+1,qr,rson(o));
tmp.p=max(max(t1.p,t2.p),t1.r+t2.l);
tmp.l=max(t1.l,t1.sum+t2.l);
tmp.r=max(t2.r,t2.sum+t1.r);
tmp.sum=t1.sum+t2.sum;
return tmp;
}//查询区间最大前缀和/后缀和,区间最大子段和,区间和。
inline int query(int l1,int r1,int l2,int r2){
if(l2>r1){
return Q(l1,r1,1,n,1).r+Q(r1+1,l2-1,1,n,1).sum+Q(l2,r2,1,n,1).l;
}//区间不重叠,直接返回
int ans=Q(l2,r1,1,n,1).p;
if(l1<l2)ans=max(ans,Q(l1,l2,1,n,1).r+Q(l2,r2,1,n,1).l-a[l2]);
if(r1<r2)ans=max(ans,Q(l1,r1,1,n,1).r+Q(r1,r2,1,n,1).l-a[r1]);
//区间重叠,分三种情况
return ans;
}
};
SMT tree;
int main(void){
int T;
scanf("%d",&T);
while(T--){
memset(a,0,sizeof(a));
memset(tree.d,0,sizeof(tree.d));
//清空
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
tree.build(1,n,1);
scanf("%d",&m);
while(m--){
int l,r,ll,rr;
scanf("%d%d%d%d",&l,&r,&ll,&rr);
printf("%d\n",tree.query(l,r,ll,rr));
}
}
return 0;
}