参照第3篇题解，样例输出两个9

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5,M=1e5+5,inf=-1e9;
int n,m;
struct E{
	int l,r,maxn,lm,rm,sum;
}e[N<<2];
int a[N],op,p,s;
inline void upd(int p)
{
	e[p].sum=e[p<<1].sum+e[p<<1|1].sum;
	e[p].lm=max(e[p<<1].sum+e[p<<1|1].lm,e[p<<1].lm);
	e[p].rm=max(e[p<<1|1].sum+e[p<<1].rm,e[p<<1|1].rm);
	e[p].maxn=max(max(e[p<<1].maxn,e[p<<1|1].maxn),e[p<<1].rm+e[p<<1|1].lm);
	return;
}
inline void build(int l,int r,int p)
{
	e[p].l=l;e[p].r=r;
	if(l==r)
	{
		e[p].lm=e[p].rm=e[p].maxn=e[p].sum=a[l];
		return;
	}
	int mid=(e[p].l+e[p].r)>>1;
	build(l,mid,p<<1);
	build(mid+1,r,p<<1|1);
	upd(p);
	return;
}
inline void change(int p,int id,int num)
{
	if(e[p].l==e[p].r)
	{
		e[p].maxn=num;
		e[p].sum=e[p].lm=e[p].rm=num;
		return;
	}
	int mid=e[p].l+e[p].r>>1;
	if(id<=mid)
		change(p<<1,id,num);
	else
		change(p<<1|1,id,num);
	upd(p);
	return;
}
inline E ask(int l,int r,int p)
{
	if(l<=e[p].l&&e[p].r<=r) return e[p];
	int mid=l+r>>1;
	if(l>mid)
		return ask(l,r,p<<1);
	if(r<=mid)
		return ask(l,r,p<<1|1);
	E a=ask(l,r,p<<1),b=ask(l,r,p<<1|1),t;
	t.sum=a.sum+b.sum;
	t.lm=max(a.sum+b.lm,a.lm);
	t.rm=max(b.sum+a.rm,b.rm);
	t.maxn=max(max(a.maxn,b.maxn),a.rm+b.lm);
	return t;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	build(1,n,1);
	while(m--)
	{
		scanf("%d",&op);
		scanf("%d%d",&p,&s);
		if(op==1)
		{
			if(p>s)
				swap(s,p);
			E ans=ask(p,s,1);
			printf("%d\n",ans.maxn);
		}
		else
			change(1,p,s);
	}
	return 0;
}