线段树【SP1043】GSS1 - Can you answer these queries I

Description

给出了序列\(A_1，A_2，…，A_n\)。 \(a_i \leq 15007，1 \leq n \leq 50000\)。查询定义如下：查询\((x，y)=max｛a_i+a{i+1}+...+a_j；x \leq i \leq j \leq y ｝\)。给定M个查询，程序必须输出这些查询的结果。

Input

输入文件的第一行包含整数\(n\)。

在第二行，\(n\)个数字跟随。

第三行包含整数\(m\)。

\(m\)行跟在后面，其中第\(1\)行包含两个数字\(x_i\)和\(y_i\)。

Output

您的程序应该输出\(m\)查询的结果，每一行一个查询。

线段树维护最大子段和裸题.

直接把我的另一篇博客粘过来

数组定义

\(lsum[ ]\)代表该区间左端点开始的最大连续和.

\(rsum[ ]\)代表该区间右端点开始的最大连续和.

\(ssum[ ]\)代表区间内最大连续和.

\(sum[ ]\) 代表区间和.

Que and A

Q:已知一个区间的左右区间的最大连续和,如何合并?

A:这个区间的最大连续和要么是左子区间的最大连续和,要么是右子区间的最大连续和.

要么是左子区间的最大右起子段和+右子区间的最大左起字段和.

code：\(ssum[o]=max(max(ssum[lson],ssum[rson]),rsum[lson]+lsum[rson])\)

Q:如何更新区间最大左起子段和.

A:新区间的最大左起子段和.要么是其左子区间最大连续和,要么是其左子区间和+右子区间的左起子段和.

最大右起子段和同理

code：\(lsum[o]=max(lsum[lson],sum[lson]+lsum[rson])\)

　　　　 \(rsum[o]=max(rsum[rson],sum[rson]+rsum[lson])\)

更新操作类似单点修改

代码中是结构体写法.

当两端不在左子节点或者右子节点的话,需要考虑合并的

代码

#include<cstdio>

#include<iostream>

#include<cctype>

#define ls o<<1

#define rs o<<1|1

#define R register

using namespace std;

inline void in(int &x)

{

	int f=1;x=0;char s=getchar();

	while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}

	while(isdigit(s)){x=x*10+s-'0';s=getchar();}

	x*=f;

}

struct cod{int l,r,lsum,rsum,sum,ssum;}tr[50008*40];

inline void up(int o)

{

	tr[o].sum=tr[ls].sum+tr[rs].sum;

	tr[o].ssum=max(max(tr[ls].ssum,tr[rs].ssum),tr[ls].rsum+tr[rs].lsum);

	tr[o].lsum=max(tr[ls].lsum,tr[ls].sum+tr[rs].lsum);

	tr[o].rsum=max(tr[rs].rsum,tr[ls].rsum+tr[rs].sum);

}

void build(int o,int l,int r)

{

	tr[o].l=l;tr[o].r=r;

	if(l==r)

	{

		in(tr[o].sum);

		tr[o].lsum=tr[o].rsum=tr[o].ssum=tr[o].sum;

		return;

	}

	int mid=(l+r)>>1;

	build(ls,l,mid);

	build(rs,mid+1,r);

	up(o);

}

cod query(int o,int x,int y)

{

	if(tr[o].l>=x and y>=tr[o].r) return tr[o];

	int mid=(tr[o].l+tr[o].r)>>1;

	if(y<=mid) return query(ls,x,y);

	if(x>mid) return query(rs,x,y);

	else

	{

		cod t,t1=query(ls,x,y),t2=query(rs,x,y);

		t.lsum=max(t1.lsum,t1.sum+t2.lsum);

		t.rsum=max(t2.rsum,t2.sum+t1.rsum);

		t.ssum=max(max(t1.ssum,t2.ssum),t1.rsum+t2.lsum);

		return t;

	}

}

int n,m;

int main()

{

	in(n);

	build(1,1,n);

	in(m);

	for(R int l,r;m;m--)

	{

		in(l),in(r);

		if(l>r)swap(l,r);

		printf("%d\n",query(1,l,r).ssum);

	}

}

巴特西

线段树【SP1043】GSS1 - Can you answer these queries I

Description

Input

Output