• 从好早之前就开始写，那时候就调不好。
• 然后每隔几天就来调一下，每次都调不好......
• 快憋出病来了......
• 别跟我提什么普朗克时间（

代码如下：

#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;
}