[数据结构与算法]公园遛狗 / 小白逛公园【ybt高效进阶4-4-3】【luogu P4513】【题解未完成】

公园遛狗 / 小白逛公园【ybt高效进阶4-4-3】【luogu P4513】【题解未完成】

题目大意：题目大意

给你一个序列，要维护两个操作。
单点修改和在一个区间中找它的最大子段和。

暂时先贴代码

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
#define r register
#define rep(i,x,y) for(r ll i=x;i<=y;++i)
#define per(i,x,y) for(r ll i=x;i>=y;--i)
using namespace std;
typedef long long ll;
const ll V=5*1e5+10;
ll a[V],n,m,k,x,y;
struct node
{
	ll ls,rs,val,len;
	#define ls(x) tree[x].ls
	#define rs(x) tree[x].rs
	#define val(x) tree[x].val
	#define len(x) tree[x].len
}tree[V<<3];
void update(ll x)
{
	val(x)=val(x<<1)+val(x<<1|1);
	ls(x)=max(ls(x<<1),val(x<<1)+ls(x<<1|1));
	rs(x)=max(rs(x<<1|1),val(x<<1|1)+rs(x<<1));
	len(x)=max(max(len(x<<1),len(x<<1|1)),ls(x<<1|1)+rs(x<<1));
}
void build(ll now,ll le,ll ri)
{
	if(le==ri)
	{
		ls(now)=rs(now)=val(now)=len(now)=a[le];
		return ;
	}
	ll mid=le+ri>>1;
	build(now<<1,le,mid);
	build(now<<1|1,mid+1,ri);
	update(now);
}
void add(ll now,ll le,ll ri,ll p,ll v)
{
	if(le==ri)
	{
		ls(now)=rs(now)=val(now)=len(now)=v;
		return ;
	}
	ll mid=le+ri>>1;
	if(p<=mid) add(now<<1,le,mid,p,v);
	else add(now<<1|1,mid+1,ri,p,v);
	update(now);
}
node ask(ll now,ll le,ll ri,ll x,ll y)
{
	if(le>=x&&ri<=y) return tree[now];
	ll mid=le+ri>>1;
	node res;
	if(mid>=y) return ask(now<<1,le,mid,x,y);
	else if(mid+1<=x) return ask(now<<1|1,mid+1,ri,x,y);
	node r1=ask(now<<1,le,mid,x,y);
	node r2=ask(now<<1|1,mid+1,ri,x,y);
	res.val=r1.val+r2.val;
	res.ls=max(r1.ls,r2.ls+r1.val);
	res.rs=max(r2.rs,r1.rs+r2.val);
	res.len=max(max(r1.len,r2.len),r1.rs+r2.ls);
	return res;
}
int main()
{
	scanf("%lld%lld",&n,&m);
	rep(i,1,n)
	 scanf("%lld",&a[i]);
	build(1,1,n);
	rep(i,1,m)
	{
		scanf("%lld%lld%lld",&k,&x,&y);
		if(k==2) add(1,1,n,x,y);
		else
		{
			if(x>y) swap(x,y);
			node ans=ask(1,1,n,x,y);
			printf("%lld\n",ans.len);
		} 
	}
	return 0;
}