题目链接

#include<bits/stdc++.h>
using namespace std;
const int N = 500010;
struct node{
	int sum,lmax,rmax,mmax;
}sgt[N*4];
int a[N];
void pushup(int index){
	sgt[index].sum = sgt[index*2].sum+sgt[index*2+1].sum;
	sgt[index].lmax = max(sgt[index*2].lmax,sgt[index*2].sum+sgt[index*2+1].lmax);
	sgt[index].rmax = max(sgt[index*2+1].rmax,sgt[index*2+1].sum+sgt[index*2].rmax);
	sgt[index].mmax = max(sgt[index*2].rmax+sgt[index*2+1].lmax,max(sgt[index].lmax,sgt[index].rmax));
}
void build(int index,int begin,int end){
	if(begin == end){
		sgt[index].sum = sgt[index].lmax = sgt[index].rmax = sgt[index].mmax =  a[begin];	
		return;
	}
	int mid = (begin+end)/2;
	build(index*2,begin,mid);
	build(index*2+1,mid+1,end);
	pushup(index);
}
void add(int index,int begin,int end,int id,int x){
	if(begin == end&&begin == id){
		sgt[index].lmax = sgt[index].mmax = sgt[index].rmax = sgt[index].sum = x;
		return;
	}
	int mid = (begin+end)/2;
	if(id <= mid){
		add(index*2,begin,mid,id,x);
	}
	else{
		add(index*2+1,mid+1,end,id,x);
	}
	pushup(index);
}
node gets(int index,int begin,int end,int l,int r){
	if(begin == l&&end == r){
		return sgt[index];
	}
	int mid = (begin+end)/2;
	if(r <= mid){
		return gets(index*2,begin,mid,l,r);
	}
	else if(mid < l){
		return gets(index*2+1,mid+1,end,l,r);
	}
	else{
		node lson = gets(index,begin,mid,l,mid);
		node rson = gets(index,mid+1,end,mid+1,r);
		node ans;
		ans.lmax = max(lson.lmax,lson.sum+rson.lmax);
		ans.rmax = max(rson.rmax,rson.sum+lson.rmax);
		ans.sum = lson.sum+rson.sum;
		ans.mmax = max(lson.rmax+rson.lmax,max(ans.lmax,ans.rmax));
		return ans;
	}
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i = 1;i <= n;i++){
		cin>>a[i];
	}
	build(1,1,n);
	while(m--){
		int op;
		cin>>op;
		if(op == 1){
			int a,b;
			cin>>a>>b;
			if(a > b)swap(a,b);
			node ans = gets(1,1,n,a,b);
			cout<<ans.mmax<<endl;
		}
		else{
			int a,b;
			cin>>a>>b;
			add(1,1,n,a,b);
		}
	}
	return 0;
}