线段树9ptsOnlyAC#1求调悬二关

#include <bits/stdc++.h>
using namespace std;
#define ll int
const int nn=5e5+5;
int n,m,a[nn],mx[4*nn];
ll s[nn],sum[4*nn];
ll lsum[4*nn],rsum[4*nn];
struct node{
	int ans,lans,rans;
}tmp,ltmp,rtmp;
node push_up(int l_l,int l_r,int r_l,int r_r,
	node l_son,node r_son){
	tmp={-1,-1,-1};
	tmp.ans=max({l_son.ans,r_son.ans,
	l_son.rans+r_son.lans});
	tmp.lans=l_son.lans;
	if(s[l_r]-s[l_l-1]==l_son.lans){
		tmp.lans=max(tmp.lans,l_son.lans+r_son.lans);
	}
	tmp.rans=r_son.rans;
	if(s[r_r]-s[r_l-1]==r_son.rans){
		tmp.rans=max(tmp.rans,r_son.rans+l_son.rans);
	}
	return tmp;
}
void push_tree(int id,int l,int r){
	int mid=(l+r)/2;
	tmp=push_up(l,mid,mid+1,r,
		node{sum[id*2],lsum[id*2],rsum[id*2]},
		{sum[id*2+1],lsum[id*2+1],rsum[id*2+1]});
	sum[id]=tmp.ans;
	lsum[id]=tmp.lans;
	rsum[id]=tmp.rans;
}
void buid(int id,int l,int r){
	if(l==r){
		sum[id]=max(0,a[l]);
		lsum[id]=a[l];
		rsum[id]=a[r];
		mx[id]=a[l];
		return;
	}
	int mid=(l+r)/2;
	buid(id*2,l,mid);
	buid(id*2+1,mid+1,r);
	push_tree(id,l,r);
	mx[id]=max(mx[id*2],mx[id*2+1]);
}
void update(int id,int l,int r,int x,int v){
	if(l==r){
		//cout<<id<<" "<<v<<" "<<l<<" "<<x<<'\n';
		sum[id]=max(0,v);
		lsum[id]=v;
		rsum[id]=v;
		mx[id]=v;
		//cout<<id<<" "<<sum[id]<<" "<<lsum[id]<<" "<<rsum[id]<<'\n';
		return;
	}
	int mid=(l+r)/2;
	if(mid>=x){
		update(id*2,l,mid,x,v);
	}else {
		update(id*2+1,mid+1,r,x,v);
	}
	push_tree(id,l,r);
	mx[id]=max(mx[id*2],mx[id*2+1]);
}
node query(int id,int l,int r,int x,int y){
	if(x<=l && r<=y){
		//cout<<"as"<<id<<" "<<sum[id]<<'\n';
		return node{sum[id],lsum[id],rsum[id]};
	}
	int mid=(l+r)/2;
	ltmp={-1,-1,-1},rtmp={-1,-1,-1};
	if(mid>=x){
		ltmp=query(id*2,l,mid,x,y);
	}if(mid<y){
		rtmp=query(id*2+1,mid+1,r,x,y);
	}
	if(ltmp.ans==-1){
		//cout<<id*2+1<<" "<<rtmp.ans<<'\n';
		return rtmp;
	}
	if(rtmp.ans==-1){
		//cout<<id*2<<" "<<ltmp.ans<<'\n';
		return ltmp;
	}
	//cout<<id<<" "<<ltmp.ans<<" "<<rtmp.ans<<'\n';
	return push_up(x,mid,mid+1,y,
		ltmp,rtmp);
}
ll find(int id,int l,int r,int x,int y){
	if(x<=l && r<=y){
		return mx[id];
	}
	int mid=(l+r)/2;
	ll ans=-2e9;
	if(mid>=x){
		ans=max(ans,find(id*2,l,mid,x,y));
	}if(mid<y){
		ans=max(ans,find(id*2+1,mid+1,r,x,y));
	}
	return ans;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		s[i]=s[i-1]+a[i];
	}
	buid(1,1,n);
	while(m--){
		int op,a,b,p,s;
		cin>>op;
		if(op==1){
			cin>>a>>b;
			if(a>b)swap(a,b);
			ll s=query(1,1,n,a,b).ans;
			if(s==0)cout<<find(1,1,n,a,b)<<'\n';
			else cout<<s<<'\n';
		}else {
			cin>>p>>s;
			update(1,1,n,p,s);
		}
	}
	return 0;
}