题目大意：维护动态带修改最大子段和。

题解：线段树额外维护合并最优解时需要的信息。

代码如下

#include <bits/stdc++.h>

using namespace std;

const int maxn=5e5+10;

inline int read(){

	int x=0,f=1;char ch;

	do{ch=getchar();if(ch=='-')f=-1;}while(!isdigit(ch));

	do{x=x*10+ch-'0';ch=getchar();}while(isdigit(ch));

	return f*x;

}

int n,m,a[maxn];

struct node{

	#define ls(x) t[x].lc

	#define rs(x) t[x].rc

	int lc,rc,sum,lmx,rmx,val;

}t[maxn<<1];

int tot,root;

inline void pushup(int o){

	t[o].sum=t[ls(o)].sum+t[rs(o)].sum;

	t[o].lmx=max(t[ls(o)].lmx,t[ls(o)].sum+t[rs(o)].lmx);

	t[o].rmx=max(t[rs(o)].rmx,t[rs(o)].sum+t[ls(o)].rmx);

	t[o].val=max(max(t[ls(o)].val,t[rs(o)].val),t[ls(o)].rmx+t[rs(o)].lmx);

}

int build(int l,int r){

	int o=++tot;

	if(l==r){t[o].sum=t[o].lmx=t[o].rmx=t[o].val=a[l];return o;}

	int mid=l+r>>1;

	ls(o)=build(l,mid),rs(o)=build(mid+1,r);

	return pushup(o),o;

}

void modify(int o,int l,int r,int pos,int val){

	if(l==r){t[o].sum=t[o].lmx=t[o].rmx=t[o].val=val;return;}

	int mid=l+r>>1;

	if(pos<=mid)modify(ls(o),l,mid,pos,val);

	else modify(rs(o),mid+1,r,pos,val);

	pushup(o);

}

node query(int o,int l,int r,int x,int y){

	if(l==x&&r==y)return t[o];

	int mid=l+r>>1;

	if(y<=mid)return query(ls(o),l,mid,x,y);

	else if(x>mid)return query(rs(o),mid+1,r,x,y);

	else{

		node ls=query(ls(o),l,mid,x,mid);

		node rs=query(rs(o),mid+1,r,mid+1,y);

		node res;

		res.sum=ls.sum+rs.sum;

		res.lmx=max(ls.lmx,ls.sum+rs.lmx);

		res.rmx=max(rs.rmx,rs.sum+ls.rmx);

		res.val=max(max(ls.val,rs.val),ls.rmx+rs.lmx);

		return res;

	}

}

void solve(){

	n=read(),m=read();

	for(int i=1;i<=n;i++)a[i]=read();

	root=build(1,n);

	while(m--){

		int opt=read(),x=read(),y=read();

		if(opt==1){

			if(x>y)swap(x,y);

			printf("%d\n",query(root,1,n,x,y).val);

		}else{

			modify(root,1,n,x,y);

		}

	}

}

int main(){

	solve();

	return 0;

}

update at 2019.3.17