SP2916 GSS5 - Can you answer these queries V 题解

原题目链接

前置知识：不带修区间最大子段和

没做过请先右转GSS1

这题比GSS1多了一个对左右端点的区间限制，GSS1的做法不再适用

这时我们就要分两种情况讨论

情况1：左右端点的区间不相交，即$[x_1,y_1]\cap[x_2,y_2]=\varnothing$

此时$[y_1+1,x_2-1]$为必选区间，我们只能最大化$[x_1,y_1]$的后缀和和$[x_2,y_2]$的前缀和，加上$[y_1+1,x_2-1]$的和即为答案

情况2：左右端点的区间相交
，即$[x_1,y_1]\cap[x_2,y_2]\ne\varnothing$

设最终答案区间左右端点分别为$x_{ans},y_{ans}$

此时答案分4种情况：

1. $\{y_1,x_2\}\subsetneqq[x_{ans},y_{ans}]$

2. $\{y_1\}\subsetneqq[x_{ans},y_{ans}]$

3. $\{x_2\}\subsetneqq[x_{ans},y_{ans}]$

4. $\{y_1,x_2\}\nsubseteqq[x_{ans},y_{ans}]$

情况1即为刚才讨论的左右端点区间不相交的情况

情况2可以最大化$[x_1,y_1]$的后缀和和$[y_1,y_2]$的前缀和求出

情况3可以最大化$[x_1,x_2]$的后缀和和$[x_2,y_2]$的前缀和求出

情况4即为求$[x_2,y_1]$的最大子段和

答案即为这4种情况中的最大值

不难发现，若情况1为最优，则情况1，2，3相等

所以情况1可以通过情况2或3来求出

代码如下

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
template<typename T> inline void read(T &x)
{
    char ch=getchar();
    T f=1;
    x=0;
    while(!('0'<=ch&&ch<='9'))
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while('0'<=ch&&ch<='9')
    {
        x=(x<<3)+(x<<1)+ch-48;
        ch=getchar();
    }
    x*=f;
}
const int N=50010;
struct sgttree
{
    int left,right,sum,ans;
}t[N<<2];
int n,m;
int a[N];
#define ls(p) p<<1
#define rs(p) p<<1|1
inline sgttree pushup(sgttree ls,sgttree rs)
{
    sgttree tmp;
    tmp.sum=ls.sum+rs.sum;
    tmp.left=max(ls.left,ls.sum+rs.left);
    tmp.right=max(rs.right,rs.sum+ls.right);
    tmp.ans=max(max(ls.ans,rs.ans),ls.right+rs.left);
    return tmp;
}
void build(int p,int l,int r)
{
    if(l==r)
    {
        t[p].ans=t[p].sum=t[p].left=t[p].right=a[l];
        return;
    }
    int mid=l+r>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    t[p]=pushup(t[ls(p)],t[rs(p)]);
}
sgttree query(int ql,int qr,int l,int r,int p)
{
    if(ql>qr)
        return (sgttree){0,0,0,0};
    if(ql<=l&&r<=qr)
    {
        return t[p];
    }
    int mid=l+r>>1;
    if(qr<=mid)
        return query(ql,qr,l,mid,ls(p));
    if(mid<ql)
        return query(ql,qr,mid+1,r,rs(p));
    sgttree ls,rs;
    if(ql<=mid)
        ls=query(ql,qr,l,mid,ls(p));
    if(mid<qr)
        rs=query(ql,qr,mid+1,r,rs(p));
    return pushup(ls,rs);
}
int main()
{
    int _;
    read(_);
    ++_;
    while(--_)
    {
        memset(t,0,sizeof(t));
    	read(n);
    	for(int i=1;i<=n;++i)
    	    read(a[i]);
    	build(1,1,n);
    	read(m);
    	++m;
    	int ll,lr,rl,rr;
    	while(--m)
    	{
    	    read(ll);
    	    read(lr);
    	    read(rl);
    	    read(rr);
    	    if(lr<rl)
    	        printf("%d\n",query(lr+1,rl-1,1,n,1).sum+query(ll,lr,1,n,1).right+query(rl,rr,1,n,1).left);
    	    else
    	    {
    	        int res=query(rl,lr,1,n,1).ans;
    	        if(ll<rl)
    	            res=max(res,query(ll,rl,1,n,1).right+query(rl,rr,1,n,1).left-a[rl]);
    	        if(rr>lr)
    	            res=max(res,query(ll,lr,1,n,1).right+query(lr,rr,1,n,1).left-a[lr]);
    	        printf("%d\n",res);
            }
    	}
    }
    return 0;
}