GSS问题(一)

又是喜闻乐见线段树内容辣!

GSS问题是一类以线段树为基础的有趣的问题

实际上这算是线段树的实际应用之一、但由于它实在经典又基础,所以实际上只是个模板题.

题面:

给出了序列 (A[1],A[2],…,A[N])。 ((a[i]≤15007,1≤N≤50000))。查询定义如下:

查询 ((x,y)=max{a[i]+a[i+1]+...+a[j];x≤i≤j≤y})。给定M个查询，程序必须输出这些查询的结果。

解释及思路

给出特定区间,让你求出其中连续一段数组之和最大是多少,如果全是正数那显然太脑残了,如果有负数就稍微难办些,正负夹杂就几乎停止思考.

但是我们曾接触过"最大子段和",一道经典的DP题,可不可以用DP来做?

DP的复杂度是(O(n)),是比较优的解法,但是我们本题有多次查询,并且每次查询的区间并不一定相同

这样一来复杂度最劣就成了(O(nm)),本题是过不了的,毕竟不可能只有1000次查询

开头即提到,本题是线段树板子题,考虑如何充分利用上线段树的特性

以下内容假设你知道线段树

重点

我们知道,线段树最为标志的结构特征就是节点多而有序,总可以代表那些不好表示的区间

同时,我们可以在这些节点上记录信息,完成区间信息的维护

对于这种"连续区间问题",我们该如何通过节点来完成维护呢

显然,每个答案区间,大概率都是由不少的节点合并而来的,

那么我们考虑,每个节点不光记录节点内的最大子段和,也记录节点左边连续最大的子段和,以及右边的.

这样一来,在进行合并的时候,将相邻两个节点的各自一端的信息进行合并就可以了

结合代码来看

代码:

#include<iostream>
#include<cstdio>
#define ll long long
#define ci const int &
using namespace std;
const int N=500005;
int n,m;
ll a[N];
struct node{
	ll l,r,maxn,sum;
	node(){
		l=r=maxn=sum=0;
	}
}nd[N<<2];
inline void build(ci k,ci l,ci r){
	if(l==r){
		nd[k].l=nd[k].r=nd[k].maxn=nd[k].sum=a[l];
		return ;
	}int mid=l+r>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	nd[k].sum=nd[k<<1].sum+nd[k<<1|1].sum;
	nd[k].l=nd[k<<1].l;
	nd[k].l=max(nd[k<<1].l,nd[k<<1].sum+nd[k<<1|1].l);
	nd[k].r=nd[k<<1|1].r;
	nd[k].r=max(nd[k<<1|1].r,nd[k<<1|1].sum+nd[k<<1].r);
	nd[k].maxn=max(max(nd[k<<1].maxn,nd[k<<1|1].maxn),nd[k<<1].r+nd[k<<1|1].l);
}
inline node query(ci k,ci l,ci r,ci x,ci y){
	if(x<=l&&r<=y) return nd[k];
	int mid=l+r>>1;
	node ret,le,ri;
	if(x<=mid) le=query(k<<1,l,mid,x,y);
	if(mid<y) ri=query(k<<1|1,mid+1,r,x,y);
	ret.sum=le.sum+ri.sum;
	if(x<=mid){
		ret.l=le.l;
		ret.l=max(le.l,le.sum+ri.l);	
	}
	else ret.l=ri.l;
	if(mid<y){
		ret.r=ri.r;
		ret.r=max(ri.r,ri.sum+le.r);	
	}else ret.r=le.r;
	if(x<=mid&&mid<y)
		ret.maxn=max(max(le.maxn,ri.maxn),le.r+ri.l);
	else if(x<=mid)
		ret.maxn=le.maxn;
	else
		ret.maxn=ri.maxn;
	return ret;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	build(1,1,n);
	scanf("%d",&m);
	while(m--){
		int l,r;
		scanf("%d%d",&l,&r);
		node ans=query(1,1,n,l,r);
		printf("%lld
",ans.maxn);
	}return 0;
}