GSS5 = GSS1 + 前缀和 + 区间最值
原题链接
其实这道题感觉评分不能上紫
建议先做一下GSS1再做这道题。
好了，我们假设你已经搞懂了GSS1，现在开始讲GSS5（
Case 1
题目给了两个区间 ([x_1,y_1], [x_2,y_2])，先考虑一下两个区间不相交的情况。
对原序列做一下前缀和，用线段树维护一下最大最小值，然后查询的时候就在 ([x_2,y_2]) 找最大，在 ([x_1-1,y_1-1]) 找最小，两者相减即可得到最大的子段和。
Case 2
如果两个区间会相交呢？显然这时候直接进行 ( ext{Case 1}) 操作是不正确的。我们对于左右端点所在的区间进行分类讨论。
首先对 ([x_1,y_1]) 和 ([y_1,y_2]) 进行 ( ext{Case 1}) 的操作，由于这里的区间只有一个元素相交，这么做不会出问题。
然后同理地，对 ([x_1,x_2]) 和 ([x_2,y_2]) 进行 ( ext{Case 1}) 的操作。
现在只剩下了查询的两个区间的交集，即 ([x_2,y_1]) 尚未处理。我们发现，这是我们要找的就是区间最大子段和，于是就可以copy下来GSS1的代码（
(small extbf{Case 1}+ extbf{Case 2} = color{green}{AC})
交了两次才过qAq，看到SPOJ下的评论好多人都一次过了。
代码：
#include <bits/stdc++.h>
using namespace std;
int T,n,m,a[50005],sum[50005];
typedef long long LL;
const int INF=0x7fffffff;
struct TreeNode
{
LL lmax,rmax,maxx;
LL sum,mn,mx;
TreeNode(): sum(0),mn(INF),mx(-INF)
{ lmax=rmax=maxx=-INF; }
TreeNode(int)
{ lmax=rmax=maxx=sum=mn=mx=0; }
}t[40005];
inline void merge(TreeNode &dst,const TreeNode &a,const TreeNode &b)
{
dst.lmax=max(a.lmax,a.sum+b.lmax);
dst.rmax=max(b.rmax,b.sum+a.rmax);
dst.maxx=max({a.maxx,b.maxx,a.rmax+b.lmax});
dst.sum=a.sum+b.sum;
dst.mn=min(a.mn,b.mn),dst.mx=max(a.mx,b.mx);
}
// 用于合并两个区间
#define LC (i<<1)
#define RC (i<<1)|1
void build(int l,int r,int i=1)
{
if(l==r)
{
t[i].sum=t[i].lmax=t[i].rmax=t[i].maxx=a[l];
t[i].mn=t[i].mx=sum[l];
// 赋初始值
}
else
{
int mid=(l+r)>>1;
build(l,mid,LC);
build(mid+1,r,RC);
merge(t[i],t[LC],t[RC]);// 合并区间
}
}
TreeNode query(int lq,int rq,int l=1,int r=n,int i=1)
{
if(lq==rq && lq==0) return TreeNode(0);
// 由于线段树在0位置没有存值，需要特殊处理
if(l>=lq && r<=rq) return t[i];
int mid=(l+r)>>1;
TreeNode res,x,y;
if(mid>=lq) x=query(lq,rq,l,mid,LC);
if(mid<rq) y=query(lq,rq,mid+1,r,RC);
merge(res,x,y);
if(lq<=0) res.mx=max(res.mx,0ll),res.mn=min(res.mn,0ll);
// 同理，对于0位置的处理
return res;
}
main()
{
scanf("%d",&T);
while(T--)
{
memset(a,0,sizeof(a));
memset(sum,0,sizeof(sum));
memset(t,0,sizeof(t));
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];
build(1,n); // 建树
scanf("%d",&m);
while(m--)
{
int l1,r1,l2,r2;
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
LL ans;
if(l2>r1)// Case 1，两区间不相交
ans=query(l2,r2).mx-query(l1-1,r1-1).mn;
else// Case 2，两区间相交
ans=max({query(l2,r2).mx-query(l1-1,l2-1).mn,// 左右端点分别在[l1,l2],[l2,r2]
query(r1,r2).mx-query(l1-1,r1-1).mn,// 左右端点分别在[l1,r1],[r1,r2]
query(l2,r1).maxx});// 查询相交部分的最大子段和
printf("%lld
",ans);
}
}
return 0;
}