9pts 玄关求助

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,m,a[N];
int ans=0;

bool f=0;
struct node{
	int l,r;
	int ans,sum;
	int lans,rans;
}rt[4*N+10];
void up(int k,int a,int b){
	rt[k].sum =rt[a].sum +rt[b].sum;
	rt[k].ans =max(rt[a].ans,rt[b].ans);
	int blans=max(rt[a].lans,rt[b].lans+rt[a].sum);
	int brans=max(rt[b].rans,rt[a].rans+rt[b].sum);
	int bans=max(rt[k].ans,rt[a].lans +rt[b].rans);
	rt[k].lans = blans;
	rt[k].rans = brans;
	rt[k].ans = bans;
}
void build(int k,int l,int r){
	rt[k].l=l,rt[k].r=r;
	//cout<<k<<" ";
	if(l==r){
		//cout<<0;//
		rt[k].lans=rt[k].rans=rt[k].ans=a[l],rt[k].sum=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(k<<1,l,mid),build(k<<1|1,mid+1,r);
	up(k,k<<1,k<<1|1);
}
void upd(int k,int p,int val){
	if(rt[k].l==rt[k].r){
		rt[k].lans=rt[k].rans=rt[k].ans=val,rt[k].sum=val;
		return;
	}
	if(p<=rt[k<<1].r)upd(k<<1,p,val);
	if(p>=rt[k<<1|1].l)upd(k<<1|1,p,val);
	up(k,k<<1,k<<1|1);
}

void gets(int k,int l,int r){
	if(l<=rt[k].l&&rt[k].r <=r){
	//	cout<<k<<" "<<rt[k].l<<" "<<rt[k].r<<" "<<rt[k].ans <<"\n";
		if(!f){
			rt[4*N+3]=rt[k];
			f=1;
		}
		else up(4*N+3,4*N+3,k);
		return;
	}
	if(l<=rt[k<<1].r)gets(k<<1,l,r);
	if(r>=rt[k<<1|1].l)gets(k<<1|1,l,r);
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int op,a,b;
		cin>>op>>a>>b;
		if(op==1){
			if(a>b)swap(a,b);
			f=0;
			gets(1,a,b);
			cout<<rt[4*N+3].ans<<"\n";
		}
		if(op==2){
			upd(1,a,b);
		}
	}
	
	
	return 0;
}