```cpp
#include<iostream>
#include<ctime>
#include<queue>
#include<stack>
#include<cmath>
#include<iterator>
#include<cctype>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<bitset>
using namespace std;
const int N=500010;
#define int long long
int n,m,w[N];
struct SMT
{
struct Node
{
int l,r,tmax,lmax,rmax,sum;
// tmax : 最大连续子段和
// lmax : 最大前缀 (maxpre)
// rmax : 最大后缀 (maxsuf)
// sum : 和（纯粹的求和）
}tr[4*N];
inline void pushup(Node& u,Node& l,Node& r)
{
u.sum=l.sum+r.sum;
u.lmax=max(l.lmax,l.sum+r.lmax);
u.rmax=max(r.rmax,r.sum+l.rmax);
u.tmax=max(max(l.tmax,r.tmax),l.rmax+r.lmax);
}
inline void pushup(int u){pushup(tr[u],tr[u<<1],tr[u<<1|1]);}
inline void build(int u,int l,int r)
{
if (l==r){tr[u]={l,r,w[r],w[r],w[r],w[r]}; return ;}
int mid=(l+r)>>1; tr[u].l=l; tr[u].r=r;
build(u<<1,l,mid); build(u<<1|1,mid+1,r);
pushup(u);
}
inline Node query(int u,int l,int r)
{
if ((tr[u].l>=l)&&(tr[u].r<=r)) return tr[u];
int mid=(tr[u].l+tr[u].r)>>1,v=0;
if (r<=mid) return query(u<<1,l,r);
if (l>mid) return query(u<<1|1,l,r);
Node ans,L=query(u<<1,l,r),R=query(u<<1|1,l,r);
pushup(ans,L,R);
return ans;
}
inline void modify(int u,int x,int v) // one point
{
if ((tr[u].l==x)&&(tr[u].r==x)) tr[u]={x,x,v,v,v,v};
else
{
int mid=(tr[u].l+tr[u].r)>>1;
if (x<=mid) modify(u<<1,x,v);
else modify(u<<1|1,x,v);
pushup(u);
}
}
}Tree;
signed main()
{
scanf("%lld%lld",&n,&m);
for (int i=1;i<=n;i++) scanf("%lld",w+i);
Tree.build(1,1,n); int k,x,y;
while (m--)
{
scanf("%lld%lld%lld",&k,&x,&y);
if (k==1)
{
if (x>y) swap(x,y);
printf("%lld\n",Tree.query(1,x,y).tmax);
}
else Tree.modify(1,x,y);
} return 0;
}
```
by Implicit @ 2020-12-06 14:01:25