Rt

#include<cstdio>
#define max(a,b) (a>b?a:b)
struct tree{
	int l,r,s,ll,rr,ss;
}a[2000005];
void push_up(int k)
{
	a[k].ss=a[k*2].ss+a[k*2+1].ss;
	a[k].ll=max(a[k*2].ll,a[k*2].ss+a[k*2+1].ll);
	a[k].rr=max(a[k*2+1].rr,a[k*2+1].ss+a[k*2].rr);
	a[k].s=max(a[k*2].rr+a[k*2+1].ll,max(a[k*2].s,a[k*2+1].s));
}
void build(int k,int l,int r)
{
	a[k].l=l;a[k].r=r;
	if(l==r)
	{
		scanf("%d",&a[k].s);
		a[k].ll=a[k].rr=a[k].ss=a[k].s;
		return;
	}
	int mid=(l+r)/2;
	build(k*2,l,mid);
	build(k*2+1,mid+1,r);
	push_up(k);
}
tree ask(int k,int l,int r)
{
	if(a[k].l>=l&&a[k].r<=r) return a[k];
	int mid=(a[k].l+a[k].r)/2;
	if(l<=mid) return ask(k*2,l,r);
	if(r>mid) return ask(k*2+1,l,r);
	tree t,x=ask(k*2,l,r),y=ask(k*2+1,l,r);
	t.ll=max(x.ll,x.ss+y.ll);
	t.rr=max(y.rr,y.ss+x.rr);
	t.s=max(x.rr+y.ll,max(x.s,y.s));
	return t;
}
void add(int k,int l,int r,int v)
{
	if(a[k].l==a[k].r)
	{
		a[k].ll=a[k].rr=a[k].ss=a[k].s=v;
		return;
	}
	int mid=(a[k].l+a[k].r)/2;
	if(l<=mid) add(k*2,l,r,v);
	if(r>mid) add(k*2+1,l,r,v);
	push_up(k);
}
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	build(1,1,n);
	while(m--)
	{
		int k,x,y;
		scanf("%d%d%d",&k,&x,&y);
		if(k==1)
		{
			if(x>y){int t=x;x=y;y=t;}
			printf("%d\n",ask(1,x,y).s);
		}
		if(k==2) add(1,x,x,y);
	}
	return 0;
}

惨烈