Lates @ 2019-12-31 18:43:58
#include<iostream>
#include<cstdio>
using namespace std;
inline int read(){
register int x=0,v=1,ch=getchar();
while(!isdigit(ch)){if(ch=='-')v=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^'0');ch=getchar();}
return x*v;
}
const int MAX=500005;
struct Node{
int ml,mr,v;
int mx;
}tree[MAX<<2];
int a[MAX];
inline int Max(int a,int b){return a>b?a:b;}
inline void pushup(int x){
tree[x].v=tree[x<<1].v+tree[x<<1|1].v;
tree[x].ml=Max(tree[x<<1].ml,tree[x<<1].v+tree[x<<1|1].ml);
tree[x].mr=Max(tree[x<<1|1].mr,tree[x<<1|1].v+tree[x<<1].mr);
tree[x].mx=Max(tree[x<<1].mx,Max(tree[x<<1|1].mx,tree[x<<1].mr+tree[x<<1|1].ml));
}
void build(int x,int l,int r){
if(l==r){
tree[x]=(Node){a[l],a[l],a[l],a[l]};
return ;
}
register int mid=l+r>>1;
build(x<<1,l,mid);build(x<<1|1,mid+1,r);
pushup(x);
}
void modify(int x,int l,int r,int s,int v){
if(l==r){
tree[x]=(Node){v,v,v,v};
return ;
}
register int mid=l+r>>1;
if(s<=mid)modify(x<<1,l,mid,s,v);
if(mid<s) modify(x<<1|1,mid+1,r,s,v);
pushup(x);
}
Node query(int x,int l,int r,int s,int t){
if(s<=l&&r<=t)return tree[x];
register int res,mid=l+r>>1;
if(s<=mid)return query(x<<1,l,mid,s,t);
else if(mid<t)return query(x<<1|1,mid+1,r,s,t);
else {
Node p=query(x<<1,l,mid,s,t),q=query(x<<1|1,mid+1,r,s,t),k;
k.v=p.v+q.v;
k.ml=Max(p.v+q.ml,p.ml);
k.mr=Max(q.v+p.mr,q.mr);
k.mx=Max(p.mr+q.ml,Max(q.mx,p.mx));
return k;
}
}
int m,n,op,l,r;
signed main(){
n=read();m=read();
for(register int i=1;i<=n;++i){
a[i]=read();
}
build(1,1,n);
while(m--){
op=read();
l=read(),r=read();
if(op==1){
if(l>r)swap(l,r);
Node tmp=query(1,1,n,l,r);
printf("%d\n",tmp.mx);
}else{
modify(1,1,n,l,r);
}
}
return 0;
}