芝士记录

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<climits>
using namespace std;

#define maxn 500000
#define ll long long
#define ls(x) (x<<1)
#define rs(x) ((x<<1) | 1)

inline ll read();

struct node{
	ll s,sl,sr,sum;
};
ll n,m;
ll base[maxn];
node t[(maxn<<2)+10];

void push_up(ll rt){
	node la=t[ls(rt)],ra=t[rs(rt)];
	t[rt].sum=la.sum+ra.sum;
	t[rt].sl=max(la.sl,la.sum+ra.sl);
	t[rt].sr=max(ra.sr,ra.sum+la.sr);
	t[rt].s=max(max(la.s,ra.s),la.sr+ra.sl);
}

void build(ll rt,ll l,ll r){
	ll mid=(l+r) >> 1;
	if(l==r){
		t[rt].sl=base[l];t[rt].sr=base[l];t[rt].s=base[l],t[rt].sum=base[l];
		return;
	}
	build(ls(rt),l,mid);
	build(rs(rt),mid+1,r);
	push_up(rt);
	//cout<<l<<" " << r<<": "<<t[rt].s<<endl;
}

void change(ll rt,ll l,ll r,ll p,ll v){
	if(l==r){
		t[rt].sl=v;t[rt].sr=v;t[rt].s=v;t[rt].sum=v;
		return;
	}
	ll mid=(l+r)>>1;
	if(p<=mid){
		change(ls(rt),l,mid,p,v);
	}
	else{
		change(rs(rt),mid+1,r,p,v);
	}
	push_up(rt);
}

node query(ll rt,ll l,ll r,ll ql,ll qr){
	if(ql<=l && r<=qr){
		return t[rt];
	}
	ll mid=(l+r)>>1;
	if(mid>=qr){
		return query(ls(rt),l,mid,ql,qr);
	}
	if(mid<ql){
		return query(rs(rt),mid+1,r,ql,qr);
	}
	node res,a,b;
	a=query(ls(rt),l,mid,ql,qr);
	b=query(rs(rt),mid+1,r,ql,qr);
	res.sl=max(a.sl,a.sum+b.sl);
	res.sr=max(b.sr,b.sum+a.sr);
	res.s=max(max(a.s,b.s),a.sr+b.sl);
	res.sum=a.sum+b.sum;
	return res;
}

int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;++i)	base[i]=read();
	build(1,1,n);
	for(int i=1;i<=m;i++){
		ll type=read();
		if(type==1){
			ll a=read(),b=read();
			node ans=query(1,1,n,min(a,b),max(a,b));
			printf("%lld\n",ans.s);
		}
		if(type==2){
			ll p=read(),v=read();
			change(1,1,n,p,v);
		}
	}
	return 0;
}
ll read(){ll w=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0' && ch<='9'){x=x*10+(ch-'0');ch=getchar();}return x*w;}