SPOJ GSS5 Can you answer these queries V ——线段树

【题目分析】

GSS1上增加区间左右端点的限制。

直接分类讨论就好了。

【代码】

#include <cstdio>

#include <cstring>

#include <cmath>

#include <cstdlib>

#include <map>

#include <set>

#include <queue>

#include <string>

#include <iostream>

#include <algorithm>

using namespace std;

#define maxn 500005

#define eps 1e-8

#define db double

#define ll long long

#define inf 0x3f3f3f3f

#define F(i,j,k) for (int i=j;i<=k;++i)

#define D(i,j,k) for (int i=j;i>=k;--i)

void Finout()

{

    #ifndef ONLINE_JUDGE

    freopen("in.txt","r",stdin);

//    freopen("out.txt","w",stdout);

    #endif

}

int Getint()

{

    int x=0,f=1; char ch=getchar();

    while (ch<'0'||ch>'9') {if (ch=='-') f=-1; ch=getchar();}

    while (ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}

    return x*f;

}

struct Node{

	int lx,rx,mx,sum;

	Node operator + (Node x)

	{

		Node ret;

		ret.lx=max(lx,sum+x.lx);

		ret.rx=max(x.sum+rx,x.rx);

		ret.sum=sum+x.sum;

		ret.mx=max(max(mx,x.mx),max(rx+x.lx,max(ret.lx,ret.rx)));

		return ret;

	}

}t[maxn];

int n,a[maxn],q,L,R;

void Build(int o,int l,int r)

{

//	printf("Build %d %d\n",l,r);

	if (l==r)

	{

		t[o].lx=t[o].rx=t[o].mx=t[o].sum=a[l];

		return ;

	}

	int mid=l+r>>1;

	Build(o<<1,l,mid);

	Build(o<<1|1,mid+1,r);

	t[o]=t[o<<1]+t[o<<1|1];

}

Node Query(int o,int l,int r)

{

//	printf("Query %d %d\n",l,r);

	if (L<=l&&r<=R) return t[o];

	int mid=l+r>>1;

	if (L>mid) return Query(o<<1|1,mid+1,r);

	else if (R<=mid) return Query(o<<1,l,mid);

	else return Query(o<<1,l,mid)+Query(o<<1|1,mid+1,r);

}

int main()

{

	int T;

	Finout();scanf("%d",&T);

	while (T--)

	{

		memset(a,0,sizeof a);

		memset(t,0,sizeof t);

		scanf("%d",&n);

		F(i,1,n) scanf("%d",&a[i]);

		Build(1,1,n);

		scanf("%d",&q);

		F(i,1,q)

		{

			int x1=Getint(),y1=Getint(),x2=Getint(),y2=Getint(),ans=0;

			if (x2>y1)

			{

				L=x1;R=y1; ans+=Query(1,1,n).rx;// printf("ans 1: %d\n",ans);

				L=x2;R=y2; ans+=Query(1,1,n).lx; //printf("ans 2: %d\n",ans);

				L=y1+1;R=x2-1; if (R>=L) ans+=Query(1,1,n).sum;//printf("ans 3: %d\n",ans);

			}

			else

			{

				int tmp=0;

				L=x2;R=y1; ans=Query(1,1,n).mx;

				if (x2>x1)

				{L=x1;R=x2-1;tmp+=Query(1,1,n).rx;}

				L=x2;R=y2; tmp+=Query(1,1,n).lx;

				ans=max(ans,tmp); tmp=0;

				L=x2;R=y1; tmp+=Query(1,1,n).rx;

				if (y2>y1)

				{L=y1+1;R=y2;tmp+=Query(1,1,n).lx;}

				ans=max(ans,tmp);

			}

			printf("%d\n",ans);

		}

	}

}