9 pts 求条

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,a[500010]; 
struct node{
	ll sum,ml,mr,ans;
}tree[2000010];
ll ls(ll p){return p<<1;}
ll rs(ll p){return p<<1|1;}
void push_up(ll p){
	tree[p].sum=tree[ls(p)].sum+tree[rs(p)].sum;
	tree[p].ml=max(tree[ls(p)].ml,tree[ls(p)].sum+tree[rs(p)].ml);
	tree[p].mr=max(tree[rs(p)].mr,tree[rs(p)].sum+tree[ls(p)].mr);
	tree[p].ans=max({tree[ls(p)].ans,tree[rs(p)].ans,tree[ls(p)].mr+tree[rs(p)].ml});
}
void build(ll p,ll pl,ll pr){
	if(pl==pr){
		tree[p].sum=a[pl];
		tree[p].ml=a[pl];
		tree[p].mr=a[pl];
		tree[p].ans=a[pl];
		return;
	}
	ll mid=(pl+pr)>>1;
	build(ls(p),pl,mid);
	build(rs(p),mid+1,pr);
	push_up(p);
}
void update(ll L,ll R,ll p,ll pl,ll pr,ll d){
	if(pl==pr){
		tree[p].sum=d;
		tree[p].ml=d;
		tree[p].mr=d;
		tree[p].ans=d;
		return;
	}
	ll mid=(pl+pr)>>1;
	if(L<=mid) update(L,R,ls(p),pl,mid,d);
	if(mid<R) update(L,R,rs(p),mid+1,pr,d);
	push_up(p);
}
node query(ll L,ll R,ll p,ll pl,ll pr){
	if(pl==pr){
		return tree[p];
	}
	ll mid=(pl+pr)>>1;
	if(R<=mid) return query(L,R,ls(p),pl,mid);
	if(mid<L) return query(L,R,rs(p),mid+1,pr);
	node tr,ansl=query(L,R,ls(p),pl,mid),ansr=query(L,R,rs(p),mid+1,pr);
	tr.sum=ansl.sum+ansr.sum;
	tr.ml=max(ansl.ml,ansl.sum+ansr.ml);
	tr.mr=max(ansr.mr,ansr.sum+ansl.mr);
	tr.ans=max({ansl.ans,ansl.ans,ansl.mr+ansr.ml});
	return tr;
}
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 k,a,b;
		cin>>k;
		if(k==1){
			cin>>a>>b;
			node tx=query(min(a,b),max(a,b),1,1,n);
			cout<<max({tx.sum,tx.ml,tx.mr,tx.ans})<<endl;
		}
		else{
			cin>>a>>b;
			update(a,a,1,1,n,b);
		}
	}
	return 0;
}