萌新 刚学 线段树 ，求助/kk/dk/kel

#include <bits/stdc++.h>
using namespace std;
int mpre[40010],msuf[40010],msum[40010],sum[40010],n,m,a[10010];
void build(int o,int lf,int rg)
{
	if(lf==rg)
	{
		msum[o]=msuf[o]=mpre[o]=max(0,a[lf]);
        sum[o]=a[lf];
		return ;
	}
	int mid=(lf+rg)>>1;
	build(o<<1,lf,mid),build(o<<1|1,mid+1,rg);
	mpre[o]=max(mpre[o<<1],sum[o<<1]+mpre[o<<1|1]);
	msuf[o]=max(msuf[o<<1|1],sum[o<<1|1]+msuf[o<<1]);
	sum[o]=sum[o<<1]+sum[o<<1|1];
	msum[o]=max(max(msum[o<<1],msum[o<<1|1]),msuf[o<<1]+mpre[o<<1|1]);
}
int qsum(int o,int lf,int rg,int l,int r)
{
	if(l>r)
	{
		return 0;
	}
	if(l<=lf&&rg<=r)
	{
		return sum[o];
	}
	int mid=(lf+rg)>>1,ans=0;
	if(l<=mid)
	{
		ans+=qsum(o<<1,lf,mid,l,r);
	}
	if(mid<r)
	{
		ans+=qsum(o<<1|1,mid+1,rg,l,r);
	}
	return ans;
}
int query(int o,int lf,int rg,int l,int r)
{
	if(l>r)
	{
		return 0;
	}
	if(l<=lf&&rg<=r)
	{
		return sum[o];
	}
	int mid=(lf+rg)>>1,ans=0;
	if(l<=mid)
	{
		ans=ans+query(o<<1,lf,mid,l,r);
	}
	if(mid<r)
	{
		ans=ans+query(o<<1|1,mid+1,rg,l,r);
	}
	return ans;
}
int qsuf(int o,int lf,int rg,int l,int r)
{
	if(l>r)
	{
		return 0;
	}
	if(l<=lf&&rg<=r)
	{
		return msuf[o];
	}
	int mid=(lf+rg)>>1,ans=0;
	if(mid<r)
	{
		ans=max(ans,qsuf(o<<1|1,mid+1,rg,l,r));
		if(l<=mid)
		{
			ans=max(ans,query(o<<1|1,mid+1,rg,l,r)+qsuf(o<<1,lf,mid,l,r));
		}
	}
	else
	{
		if(l<=mid)
		{
			ans=max(ans,qsuf(o<<1,lf,mid,l,r));
		}
	}
	return ans;
}
int qpre(int o,int lf,int rg,int l,int r)
{
	if(l>r)
	{
		return 0;
	}
	if(l<=lf&&rg<=r)
	{
		return mpre[o];
	}
	int mid=(lf+rg)>>1,ans=0;
	if(l<=mid)
	{
		ans=max(ans,qpre(o<<1,lf,mid,l,r));
		if(mid<r)
		{
			ans=max(ans,query(o<<1,lf,mid,l,r)+qpre(o<<1|1,mid+1,rg,l,r));
		}
	}
	else
	{
		if(mid<r)
		{
			ans=max(ans,qpre(o<<1|1,mid+1,rg,l,r));
		}
	}
	return ans;
}
int qans(int o,int lf,int rg,int l,int r)
{
	if(l>r)
	{
		return 0;
	}
	if(l<=lf&&rg<=r)
	{
		return msum[o];
	}
	int mid=(lf+rg)>>1,ans=0;
	if(l<=mid&&mid<r)
	{
		ans=qsuf(o<<1,lf,mid,l,r)+qpre(o<<1|1,mid+1,rg,l,r);
	}
	if(l<=mid)
	{
		ans=max(ans,qans(o<<1,lf,mid,l,r));
	}
	if(mid<r)
	{
		ans=max(ans,qans(o<<1|1,mid+1,rg,l,r));
	}
	return ans;
}
int T;
int main()
{
	cin>>T;
	while(T--)
	{
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
		}
		cin>>m;
		build(1,1,n);
		for(int i=1;i<=m;i++)
		{
			int l1,r1,l2,r2;
			scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
			if(r1<l2)
			{
				cout<<qsum(1,1,n,r1+1,l2-1)+qsuf(1,1,n,l1,r1)+qpre(1,1,n,l2,r2)<<"\n";
			}
			else
			{
				int val=qans(1,1,n,l2,r1);
				if(l1<l2)
				{
					val=max(val,qsuf(1,1,n,l1,l2)+qpre(1,1,n,l2,r2)-a[l2]);
				}
				if(r1<r2)
				{
					val=max(val,qpre(1,1,n,r1,r2)+qsuf(1,1,n,l1,r1)-a[r1]);
				}
				cout<<val<<"\n";
			}
		}
	}
}