P4513 小白逛公园 线段树

链接

小白逛公园
题目大意：对区间进行单点修改和子区间最大权值的查询

思路

可以用线段树来维护子区间的最大权值。
当查询区间的子区间最大权值时，设其左区间为，右区间为，中间点为。
的子区间最大权值可能来自以下三种情况：

1. 完全来自；
2. 完全来自；
3. 从左区间取一段，从右区间取一段，且该区间跨过；

对于情况和情况

的答案即对应左区间和右区间的答案。

对于情况

设为区间的最大后缀和，为区间的最大前缀和，那么这段区间就是。
如下图所示：

如何维护区间的和(下面以的维护为例，自己思考的维护)

1. 当为叶结点时，很显然的叶结点的值；
2. 否则，的可以完全是左区间的，也可以是左区间的总和加上右区间的。 可得：；
   综上，一个线段树的结点需要保存的内容有：
   ；
   其中和分别为左右端点，为维护的答案。

其他

更新递归后结点时千万不要对当前结点取。
因为对子区间进行修改之后有可能为负值。

代码

#include<bits/stdc++.h>
#define l(p) t[p].l
#define r(p) t[p].r
#define sum(p) t[p].sum
#define bst(p) t[p].bst
#define pre(p) t[p].pre
#define lst(p) t[p].lst
#define lc p<<1
#define rc p<<1|1
using namespace std;
const int N=500000+10;
struct Node{
	int l,r,sum,bst,pre,lst;
}t[4*N];
int n,m,k,x,y;
int a[N];
inline int max_(int q,int w,int e)
{
	q=(q>w)?q:w;
	q=(q>e)?q:e;
	return q;
}
inline int read()
{
	int ret=0,flag=1;char ch=getchar();
	while(ch<'0' || ch>'9')
	{
		if(ch=='-')flag=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9')ret=ret*10+ch-'0',ch=getchar();
	return ret*flag;
}
inline void update(int p)		//更新结点p 
{
	sum(p)=sum(lc)+sum(rc);
	pre(p)=max(pre(lc),sum(lc)+pre(rc));
	lst(p)=max(lst(rc),sum(rc)+lst(lc));
	bst(p)=max_(bst(lc),bst(rc),lst(lc)+pre(rc));
}
inline void sete(int p,int val)	//为叶结点赋值 
{
	sum(p)=bst(p)=pre(p)=lst(p)=val;
}
void build(int p)
{
	if(l(p)==r(p))
	{
		sete(p,a[l(p)]);
		return;
	}
	int mid=(l(p)+r(p))>>1;
	l(lc)=l(p);r(lc)=mid;
	l(rc)=mid+1;r(rc)=r(p);
	build(lc);
	build(rc);
	update(p);
}
void modify(int p,int aim,int val)	//修改操作 
{
	if(l(p)==aim && r(p)==aim)		//如果到达叶结点且是目标位置 
	{
		sete(p,val);
		return;
	}
	int mid=(l(p)+r(p))>>1;
	if(aim<=mid)modify(lc,aim,val);
	else modify(rc,aim,val);
	update(p);
}
Node query(int p,int al,int ar)	//查询操作 
{
	if(al<=l(p) && ar>=r(p))
	return t[p];
	Node ret=(Node){0,0,0,0,0,0};
	int mid=(l(p)+r(p))>>1;
	if(ar<=mid)return query(lc,al,ar);
	else if(al>mid)return query(rc,al,ar);
	else
	{
		Node lft=query(lc,al,ar);
		Node rht=query(rc,al,ar);
		ret.bst=max_(lft.bst,rht.bst,lft.lst+rht.pre);
		ret.pre=max(lft.pre,lft.sum+rht.pre);
		ret.lst=max(rht.lst,rht.sum+lft.lst);
		ret.sum=lft.sum+rht.sum;
		return ret;
	}
}
int main()
{
	n=read();m=read();
	for(register int i=1;i<=n;++i)
	a[i]=read();
	l(1)=1;r(1)=n;
	build(1);
	while(m--)
	{
		k=read();x=read();y=read();
		if(x>y && k==1)swap(x,y);
		if(k==1)
		{
			printf("%d\n",query(1,x,y).bst);
		}
		else modify(1,x,y);
	}
}