zkw线段树46pts求助

#include <iostream>
using namespace std;
#define int long long
const int N = 5e5+10, inf = 1010;
struct Segment_Tree{ int m, l, r, s; } st[N<<4];	// s:all, m:max, l:lmax, r:rmax
inline Segment_Tree merge(Segment_Tree a, Segment_Tree b) {
	return {
		max(max(a.m, b.m), a.r+b.l),
		max(a.l, a.s+b.l),
		max(b.r, b.s+a.r),
		a.s+b.s
	};
}
#define le (u<<1)
#define ri (u<<1|1)
int n, m, tn, a[N];
inline void build() {
	for(tn=1;tn<=n+1;tn<<=1);
	for(int i=1;i<=n;++i) st[i+tn] = {a[i], a[i], a[i], a[i]};
	for(int u=tn-1;u;--u) st[u]=merge(st[le], st[ri]);
}
inline void update(int u, int v) {
	u+=tn, st[u] = {v, v, v, v};
	for(u>>=1;u;u>>=1) st[u]=merge(st[le], st[ri]);
}
inline int query(int l, int r) {
	Segment_Tree ansl = {-inf,-inf,-inf,-inf};
	Segment_Tree ansr = {-inf,-inf,-inf,-inf};
	for(l+=tn-1,r+=tn+1;l^r^1;l>>=1,r>>=1) {
		if(~l&1) ansl = ansl.s==-inf?st[l^1]:merge(ansl, st[l^1]);
		if(r&1) ansr = ansr.s==-inf?st[r^1]:merge(st[r^1], ansr);
	}
	if(ansl.s==-inf) return ansr.m;
	if(ansr.s==-inf) return ansl.m;
	return merge(ansl, ansr).m;
}
signed main() {
	cin>>n>>m;
	for(int i=1;i<=n;++i) cin>>a[i];
	build();
	while(m--) {
		int k; cin>>k;
		if(k==1) {
			int a, b; cin>>a>>b;
			if(a > b) swap(a, b);
			cout<<query(a, b)<<"\n";
		} else {
			int p, s; cin>>p>>s;
			update(p, s);
		}
	}
	return 0;
}