关于GSS

SPOJ上一个专题，名为Can you answer these queries，包含线段树，平衡树，树链剖分的练习共8道

GSS1

传送门

题目大意

你有一个序列$A[1],A[2],\dots A[n]$,有$m$次询问,每次询问一个序列$(x,y)$,请你求出一组$(i,j)$，要求$x\le i\le j\le y$，使得$A[i]+A[i+1]+\dots +A[j]$的值最大,输出这个值。$(n\le 5\times 10^4)$

解析

对于一个区间和问题,我们可以用一种非常漂亮的方法求解.

我们如果把一个区间拆成两个相邻的区间,那么取到该区间的最大值的那个区间不外乎$3$种情况:

$1.$只在划分出的左区间

$2.$只在划分出的右区间

$3.$同时跨越左区间和右区间

如下图所示：

对于$1,2$种情况的处理方式比较简单,直接记录每一个区间的最大值再合并即可.

对于我们的情况$3$,容易发现情况3的区间是由两段区间拼合而成的.第一段为左区间的一段后缀,第二段为右区间的一段前缀,容易得出该后缀与前缀均为左右区间的最长后缀与最长前缀.

想到上述解法后问题就不难了.

观察一下区间的划分方式,是可以用一棵线段树来维护的,具体来说,这棵线段树需要记录$4$个值,区间最长前缀$prefix$,最长后缀$suffix$,区间和$sum$,区间最大区间和$maxn$

实现

有了具体思路,下面让我们考虑上传操作.

$prefix$与$suffix$的处理较简单,需分两种情况,这里以$prefix$为例:

$1.$左区间的最长前缀

$2.$右区间的最长前缀+左区间数的总和

$suffix$同理

$maxn$的处理也不是太困难,还记得前面的那张图吗?

情况$1$:左区间的最大值

情况$2$:右区间的最大值

情况$3$:左区间的最长后缀+右区间的最长前缀.

三种情况都可以在$O(1)$时间内处理.

$sum$的上传直接用左区间的$sum$加右区间的$sum$.

对于一个结点,查询操作中将其划分为左区间和右区间,先将查询到的值存下来,然后按照合并操作时的方法求出其并集的四个值即可.

注意在只查询左区间或右区间时直接返回查询值即可,无需合并.

总时间复杂度:$O(nlogn)$

GSS3

传送门

题目大意：

同GSS1，增加单点修改操作。

解析

用同样的手法,加入普通的单点查询操作即可,记得pushup.

Code

//GSS1
#include<bits/stdc++.h>
using namespace std;
struct node{int l,r;int prefix,suffix,maxn,sum;
}seg[400005];
int n,m,a[100005];
void pushup(int o){seg[o].prefix=max(seg[o<<1].prefix,seg[o<<1].sum+seg[o<<1|1].prefix);seg[o].suffix=max(seg[o<<1|1].suffix,seg[o<<1|1].sum+seg[o<<1].suffix);seg[o].maxn=max(seg[o<<1].maxn,seg[o<<1|1].maxn);seg[o].maxn=max(seg[o].maxn,seg[o<<1].suffix+seg[o<<1|1].prefix);seg[o].sum=seg[o<<1].sum+seg[o<<1|1].sum;
}
void build(int o,int l,int r){seg[o].l=l,seg[o].r=r;if(l==r){seg[o].prefix=seg[o].suffix=seg[o].maxn=seg[o].sum=a[l];return ;}int mid=(l+r)>>1;build(o<<1,l,mid);build(o<<1|1,mid+1,r);pushup(o);
}
node query(int o,int nl,int nr){if(nl<=seg[o].l&&seg[o].r<=nr)  return seg[o];int mid=(seg[o].l+seg[o].r)>>1;node tmp,tmp1,tmp2;int cnt=0;if(nl<=mid){if(mid>=nr)  return query(o<<1,nl,nr);node lc=query(o<<1,nl,nr),rc=query(o<<1|1,nl,nr),tmp;tmp.prefix=max(lc.prefix,lc.sum+rc.prefix);tmp.suffix=max(rc.suffix,rc.sum+lc.suffix);tmp.maxn=max(max(lc.maxn,rc.maxn),lc.suffix+rc.prefix);tmp.sum=lc.sum+rc.sum;return tmp;}return query(o<<1|1,nl,nr);
}
int main(){scanf("%d",&n);for(int i=1;i<=n;++i){scanf("%d",&a[i]);}build(1,1,n);scanf("%d",&m);for(int i=1;i<=m;++i){int x,y;scanf("%d%d",&x,&y);node s=query(1,x,y);printf("%d\n",max(max(s.prefix,s.suffix),s.maxn));}
}

//modify操作
void modify(int o,int pos,int x){if(seg[o].l==seg[o].r){seg[o].prefix=seg[o].suffix=seg[o].maxn=seg[o].sum=x;return ;}int mid=(seg[o].l+seg[o].r)>>1;if(pos<=mid)  modify(o<<1,pos,x);else  modify(o<<1|1,pos,x);pushup(o);
}