SPOJ GSS5 Can you answer these queries V （線段樹）

比GSS3 麻煩在於要判斷兩個區間的相交性。

分為三種情況.

1. x1 y1 x2 y2

這種情況就是 x1 y1 的右最大 + sum【y1 x2】 + x2 y2的做最大

2.x1 x2 y2 y1 其實就是 y1==y2的時候

要麼區間在 x2-y2之間

要麼區間的頭在 x1 x2之間，尾在 x2 y2之間

3. x1 x2 y1 y2。

這種情況和2比較像是 這個時候 x1-y2 區間分成三段。只需要枚舉頭尾各在區間哪個區間就好了。

需要注意的是。 有可能 x2==y1

所以要注意一下比較的時候的邊界。

#include 
#include 
#include 
#include 
#define maxn 11111
#define lson num<<1,s,mid
#define rson num<<1|1,mid+1,e

using namespace std;

int tre[maxn<<2];
int lef[maxn<<2];
int rig[maxn<<2];
int sum[maxn<<2];

void pushup(int num)
{
    sum[num]=sum[num<<1]+sum[num<<1|1];
    lef[num]=max(lef[num<<1],sum[num<<1]+lef[num<<1|1]);
    rig[num]=max(rig[num<<1|1],sum[num<<1|1]+rig[num<<1]);
    tre[num]=max(tre[num<<1],max(tre[num<<1|1],lef[num<<1|1]+rig[num<<1]));
}
void build(int num,int s,int e)
{
    if(s==e)
    {
        scanf("%d",&tre[num]);
        lef[num]=rig[num]=sum[num]=tre[num];
        return;
    }
    int mid=(s+e)>>1;
    build(lson);
    build(rson);
    pushup(num);
}

int Q_sum(int num,int s,int e,int l,int r)
{
    if(l>r)return 0;
    if(l<=s && r>=e)
    {
        return sum[num];
    }
    int mid=(s+e)>>1;
    if(r<=mid)return Q_sum(lson,l,r);
    else if(l>mid)return Q_sum(rson,l,r);
    else
    {
        return Q_sum(lson,l,mid)+Q_sum(rson,mid+1,r);
    }
}

int Q_L(int num,int s,int e,int l,int r)
{
    if(l>r)return 0;
    if(l<=s && r>=e)
    {
        return lef[num];
    }
    int mid=(s+e)>>1;
    if(r<=mid)return Q_L(lson,l,r);
    else if(l>mid)return Q_L(rson,l,r);
    else return max(Q_L(lson,l,mid),max(Q_sum(lson,l,mid),Q_sum(lson,l,mid)+Q_L(rson,mid+1,r)));
}
int Q_R(int num,int s,int e,int l,int r)
{
    if(l>r)return 0;
    if(l<=s && r>=e)
    {
        return rig[num];
    }
    int mid=(s+e)>>1;
    if(r<=mid)return Q_R(lson,l,r);
    else if(l>mid)return Q_R(rson,l,r);
    else return max(Q_R(rson,mid+1,r),max(Q_sum(rson,mid+1,r),Q_sum(rson,mid+1,r)+Q_R(lson,l,mid)));
}
int query(int num,int s,int e,int l,int r)
{
    if(l>r)return 0;
    if(l<=s && r>=e)
    {
        return tre[num];
    }
    int mid=(s+e)>>1;
    if(r<=mid)return query(lson,l,r);
    else if(l>mid)return query(rson,l,r);
    else
    {
        return max(Q_L(rson,mid+1,r)+Q_R(lson,l,mid),max(query(lson,l,mid),query(rson,mid+1,r)));
    }
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        build(1,1,n);
        int m;
        scanf("%d",&m);
        while(m--)
        {
            int x1,x2,y1,y2;
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            if(x2>y1)
            {
                printf("%d\n",Q_R(1,1,n,x1,y1)+Q_sum(1,1,n,y1+1,x2-1)+Q_L(1,1,n,x2,y2));
            }
            else if(y1==y2)
            {
                printf("%d\n",max(query(1,1,n,x2,y2),Q_L(1,1,n,x2,y2)+Q_R(1,1,n,x1,x2-1)));
            }
            else
            {
                printf("%d\n",max(Q_R(1,1,n,x1,x2-1)+Q_L(1,1,n,x2,y1),max(Q_R(1,1,n,x1,x2-1)+Q_L(1,1,n,y1+1,y2)+Q_sum(1,1,n,x2,y1),max(Q_R(1,1,n,x2,y1)+Q_L(1,1,n,y1+1,y2),query(1,1,n,x2,y1)))));
            }
        }
    }
    return 0;
}
/*
3
6 3 -2 1 -4 5 2
2
1 3 4 5
*/