• 大概就是分类讨论
• 首先是区间不重叠，那么就是左边的最大后缀+中间的区间和+右边的最大前缀
• 然后是重叠的话，那么还要分类讨论
• 思路和这篇题解差不多。
• 但是样例都过不去....../kel/kel
• 调了快半小时了，要疯了（
• 这次没有刚学OI $\sout{10^{-998244353}}$ ms了（
• 代码如下：

#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;
	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<=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 l2,int r1,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;
}