给定长度为 N 的数列 A，以及 M 条指令，每条指令可能是以下两种之一：
1 x y，查询区间 [x,y] 中的最大连续子段和。
2 x y，把 A[x] 改成 y。
对于每个查询指令，输出一个整数表示答案。
输入
第一行两个整数 N,M (N ≤ 500000,M ≤ 100000)。
第二行 N 个整数 A[i] (?1000 ≤ A[i] ≤ 1000)。
接下来 M 行每行 3 个整数 k,x,y，k=1 表示查询（此时如果 x>y，请交换 x,y），k=2 表示修改。
输出
对于每个查询指令输出一个整数表示答案。
每个答案占一行。
Input
5 3
1 2 -3 4 5
1 2 3
2 2 -1
1 3 2
Output
2
-1
解析：
要想维护当前区间的最大连续子段和，需要知道 左子区间的最大连续子段和、右子区间的最大连续子段和、横跨两区间的左子最大后缀和+右子前缀和，
在这三个数中取最大，就是当前区间的最大连续子段和；
而维护区间的最大前缀和，需要知道左子区间的最大前缀和、左子区间的总和+右子区间的最大前缀和，
在这两个数中取最大，就是当前区间的最大前缀和；
而维护区间的最大后缀和，需要知道右子区间的最大后缀和、右子区间的总和+左子区间的最大后缀和，
在这两个数中取最大，就是当前区间的最大后缀和。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pair<int,int> PII;
const double PI=acos(-1.0);
const int N=2e6+10;
struct node
{
int l,r;
int tmax,lmax,rmax,sum; //记录当前区间的最大连续子段和、最大前缀和、最大后缀和、总和.
}tr[4*N];
int n,m;
int a[N];
void pushup (node& u,node& l,node& r) //重载，引用修改
{
u.tmax=max({l.tmax,r.tmax,l.rmax+r.lmax}); //更新当前区间的最大连续子段和 max({左子区间的tmax,右子区间的tmax,横跨俩区间的rmax+lmax});
u.lmax=max(l.lmax,l.sum+r.lmax); //更新当前区间的最大前缀和 max(左子区间的lmax,左子区间的sum+右子区间的lmax);
u.rmax=max(r.rmax,r.sum+l.rmax); //更新当前区间的最大后缀和 max(右子区间的rmax,右子区间的sum+左子区间的rmax);
u.sum=l.sum+r.sum; //更新当前区间的总和 左子区间的sum+右子区间的sum.
}
void pushup(int u)
{
pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}
void build(int u,int l,int r)
{
if (l==r) tr[u]={l,l,a[l],a[l],a[l],a[l]};
else
{
tr[u]={l,r};
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
}
void modify(int u,int x,int v)
{
if (tr[u].l==tr[u].r&&tr[u].l==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);
}
}
node query(int u,int l,int r)
{
if (tr[u].l>=l&&tr[u].r<=r) return tr[u];
else
{
int mid=tr[u].l+tr[u].r>>1;
if (r<=mid) return query(u<<1,l,r); //如果[l,r]完全在左半边，返回左子的最大连续子段和
else if (l>mid) return query(u<<1|1,l,r); //如果[l,r]完全在右半边，返回右子的最大连续子段和
else
{ //如果[l,r]在 mid 的左右两边,
node left=query(u<<1,l,r); //比较左子的最大连续子段和、右子的最大连续子段和、横跨两区间的左子最大后缀和+右子前缀和
node right=query(u<<1|1,l,r);
node res;
pushup(res,left,right);
return res;
}
}
}
void solve()
{
cin>>n>>m;
for (int i=1;i<=n;i++) cin>>a[i];
build(1,1,n);
int k,x,y;
while (m--)
{
cin>>k>>x>>y;
if (k==1)
{
if (x>y) swap(x,y);
cout<<query(1,x,y).tmax<<endl;
}
else modify(1,x,y);
}
}
signed main()
{
ios;
int T=1;
//cin>>T;
while (T--) solve();
return 0;
}