Sicily 1136 山海经 (SOJ 1136)「Segment Tree 线段树」

0.00 avg. rating (0% score) - 0 votes
转载请注明: 吹水小镇 | reetsee.com
原文链接地址: http://blog.reetsee.com/archives/43

原题地址:点击打开链接

这题花了整整一天来做,错误基本都是TLE,但是做完非常哈皮,因为感觉比较好地运用了线段树这个数据结构。话说这几天广东不是一般热,中午根本睡不着,满身黏糊糊,课室和图书馆倒成了平时宅男的去处,不过这仅仅限于他们宿舍没有开空调的情况下·····然后昨天的过劳导致了今天的脖子和肩膀连成一片的疼,而且我能明显感觉到头脑恍惚。

呃,这题我感觉是可以好好写,但是感觉现在写解题报告好像变懒了,懒不得懒不得,等会儿妹子下课了去吃个雪糕,夏日已来么?

————————正文————————

我看了一下网上各位大牛的代码,可以说我的代码还是比较短的,当然也达到了120行的水平,哎可能是“自家孩子最漂亮”的缘故,哈哈,若有冒犯多多包涵。

这题的数据设计得非常恰到好处,就掐着你O(n^2)的算法肯定是过不了的,数据一点都不水。下面说下这题的思路。

线段树其实是个比较容易弄懂的东西,在这题上面,唯一的难点就是如果查询的范围刚好跨了两棵子树怎么办?下面以有5个数字的序列举例,其线段树如下:

线段树1

上面每个节点都保存了这一段的最大连续和(smax),获得最大连续和时的左下标和右下标(sl和sr)。

最大连续和smax怎么来?

1. 可能是从左子树来

2. 可能是从右子树来

3. 可能是:左子树中包含最右序号的最大连续和+右子树中包含最左序号的最大连续和

对于节点(1,5),如果碰到情况3,那么就要知道:a. 当前节点的左儿子在包含最右序号(即3)时的最大连续值; b. 以及右儿子在包含最左序号(即4)时的最大连续值,然后相加即可。

将a中的值保存在节点的rmax中,而达到rmax时的左序号保存在rmn中;同理将b中的值保存在节点的lmax中,达到lmax时的右序号保存在lmn中。

(说了这么多,是不是觉得很乱,其实不用太过咬文嚼字,先有个大概想下你觉得应该是怎么计算的,然后再来套上面这些文字。)

现在另外一个问题来了,怎么计算rmax和lmax?如果每次都额外再用O(N)的算法来计算当前节点的lmax和rmax,那么会超时,为什么呢,粗略可以估计一下线段树的节点数是2N,如果对每个节点都使用O(N)的算法来计算那么将会达到O(N^2)复杂度,会直接卡死。所以要找O(1)的方法。

其实稍微思考下,当前节点的lmax,rmax可以由两个子节点得到,lmax不外乎以下2种情况:

1. 左儿子的所有元素和+右儿子的lmax

2. 左儿子的lmax

rmax同理,所以这个问题也解决了。

 

如果我查(2, 5)的最大连续和那怎么办?很明显这个查询在去到(1,5)的时候就会卡住,我们知道,其实(1,5)的最大值可能是以下三种情况之一:

1. 可能是(2,3)的最大值

2. 可能是(4,5)的最大值

3. 可能是(2,5)中同时包含下标3和4的子集的最大值,如(2,4),(2,5),(3,4),(3,5)

我们使用的是递归查找,情况1和情况2都可以直接往下走,因为这两种情况下序列的范围是儿子节点的序列范围的子集

对于情况3,其实十分类似找lmax与rmax,但是要计算必须知道子节点的lmax与rmax,(2,5)的子节点是什么?问得好,其实我们对于每一个查询,重新建立一棵临时的树就好了,要注意的是这棵树可能不是平衡的,可能左树高点,可能右树高点,但是计算方法是一样的。对于(2,5),临时的线段树如下:

线段树2

这棵树的建立方法基本相同,具体参见代码即可,看懂了上面代码也非常容易看明白了。多说一句,用cin和cout会超时

代码如下:

#include<iostream>
#include<algorithm>
#include<stdio.h>
#define RANGE 100005
#define INF 0x7fffffff
using namespace std;
struct node
{
	int l,r,sum;            //当前节点左边界、右边界、元素总和
	int lmn,rmn,lmax,rmax;  //从左边界开始连续到第lmn位置元素和,有最大值lmax
							//从右边界开始连续到第rmn位置元素和,有最大值rmax
	int lson,rson;			//节点左儿子和右儿子的编号
	int sl,sr,smax;         //当前序列从sl到sr能取得最大连续值smax
}nn[RANGE*6];				//输入的线段树需要的空间为2*N(开3*N的数组),计算时建立新树,故翻倍
int n,m,a[RANGE*2];
int nnum;                   //每次解决查询时,建立新的线段树节点的开始下标

void computeMax(int index, int ls, int rs)//计算index节点的sum,sl,sr,smax,lmn,lmax,rmn,rmax
{
	 int tmp;
	 nn[index].sum=nn[ls].sum+nn[rs].sum;

	 nn[index].smax=nn[ls].smax;
	 nn[index].sl=nn[ls].sl;
	 nn[index].sr=nn[ls].sr;
	 tmp=nn[ls].rmax+nn[rs].lmax;
	 if(tmp>nn[index].smax || (tmp==nn[index].smax && nn[ls].rmn<nn[index].sl))
	 {
		nn[index].smax=nn[ls].rmax+nn[rs].lmax;
		nn[index].sl=nn[ls].rmn;
		nn[index].sr=nn[rs].lmn;
	 }
	 if(nn[rs].smax>nn[index].smax)
	 {
		nn[index].smax=nn[rs].smax;
		nn[index].sl=nn[rs].sl;
		nn[index].sr=nn[rs].sr;
	 }

	 //计算当前节点的lmax与rmax
	 tmp=nn[ls].sum+nn[rs].lmax;
	 if(tmp>nn[ls].lmax)
	 {
		 nn[index].lmax=tmp;
		 nn[index].lmn=nn[rs].lmn;
	 }
	 else
	 {
		 nn[index].lmax=nn[ls].lmax;
		 nn[index].lmn=nn[ls].lmn;
	 }
	 tmp=nn[rs].sum+nn[ls].rmax;
	 if(tmp>=nn[rs].rmax)//注意等于号
	 {
		 nn[index].rmax=tmp;
		 nn[index].rmn=nn[ls].rmn;
	 }
	 else
	 {
		 nn[index].rmax=nn[rs].rmax;
		 nn[index].rmn=nn[rs].rmn;
	 }
}
int compute(int l, int r, int index)
{
	if(l==nn[index].l && r==nn[index].r)
	 return index;

	int ls=index*2;		//左二子标号
	int rs=index*2+1;   //右儿子标号
	if(r<=nn[ls].r)
		return compute(l,r,ls);
	else if(l>=nn[rs].l)
		return compute(l,r,rs);
	else
	{
		int nindex=nnum++;
		nn[nindex].l=l; nn[nindex].r=r;
		nn[nindex].lson=compute(l,nn[ls].r,ls);
		nn[nindex].rson=compute(nn[ls].r+1,r,rs);
		computeMax(nindex, nn[nindex].lson, nn[nindex].rson);
		return nindex;
	}
}
void buildTree(int l, int r, int index)
{
	 nn[index].l = l;
	 nn[index].r = r;
	 if(l==r)
	 {
		 nn[index].sum=nn[index].smax=nn[index].lmax=nn[index].rmax=a[l];
		 nn[index].lmn=nn[index].rmn=nn[index].sl=nn[index].sr=l;
		 return;
	 }
	 int mid=(l+r)/2;
	 int ls,rs;   //左右儿子编号
	 ls=index*2; rs=index*2+1;
	 buildTree(l,mid,ls);
	 buildTree(mid+1,r,rs);

	 computeMax(index, ls, rs);
}
int main()
{
	//freopen("in","r",stdin);
	//freopen("out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
	 scanf("%d",&a[i]);
	buildTree(1,n,1);
	for(int i=1;i<=m;++i)
	{
		int tmpa,tmpb;
		scanf("%d%d",&tmpa,&tmpb);
		nnum=3*n+1;
		int nindex = compute(tmpa,tmpb,1);
		printf("%d %d %d\n", nn[nindex].sl, nn[nindex].sr, nn[nindex].smax);
	}
}

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注