给定长度为N的数列A，以及M条指令，每条指令可能是以下两种之一：
1、“1 x y”，查询区间 [x,y] 中的最大连续子段和，即 maxx≤l≤r≤y{∑ri=lA[i]}。
2、“2 x y”，把 A[x] 改成 y。
对于每个查询指令，输出一个整数表示答案。
输入格式
第一行两个整数N,M。
第二行N个整数A[i]。
接下来M行每行3个整数k,x,y，k=1表示查询（此时如果x>y，请交换x,y），k=2表示修改。
输出格式
对于每个查询指令输出一个整数表示答案。
每个答案占一行。
数据范围
N≤500000,M≤100000
输入样例：
5 3
1 2 -3 4 5
1 2 3
2 2 -1
1 3 2
输出样例：
2
-1
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 5e5+5;
struct node {int l,r;ll tmax,lsum,rsum;//分别为最大连续子段和，最大前缀和，最大后缀和ll sum;//维护的区间上数的和
}tr[N<<2];
int a[N];
void push_up(node &k,node &l,node &r) {k.sum = l.sum + r.sum;k.lsum = max(l.lsum,l.sum + r.lsum);k.rsum = max(r.rsum,r.sum + l.rsum);k.tmax = max(max(l.tmax,r.tmax),l.rsum + r.lsum);
}
void push_up(int k) {push_up(tr[k],tr[k<<1],tr[k<<1|1]);
}
void build(int k,int l,int r) {if(l == r) tr[k] = {l,r,a[l],a[l],a[l],a[l]};else {tr[k] = {l,r};int mid = l + r >> 1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);push_up(k);}
}
node query(int k,int l,int r) {if(tr[k].l >= l && tr[k].r <= r) return tr[k];else {int mid = tr[k].l + tr[k].r >> 1;if(r <= mid) return query(k<<1,l,r);else if(l > mid) return query(k<<1|1,l,r);else {node res,left,right;left = query(k<<1,l,r);right = query(k<<1|1,l,r);push_up(res,left,right);return res;} }
}
void modify(int k,int x,int y) {if(tr[k].l == x && tr[k].r == x) tr[k] = {x,x,y,y,y,y};else {int mid = tr[k].l + tr[k].r >> 1;if(x <= mid) modify(k<<1,x,y);else modify(k<<1|1,x,y);push_up(k);}
}
int main() {int n,m;cin >> n >> m; for(int i=1;i<=n;i++) cin >> a[i];build(1,1,n);while(m--) {int op,x,y;cin >> op >> x >> y;if(op == 1) {if(x > y) swap(x,y);cout << query(1,x,y).tmax << endl;}else{modify(1,x,y);}}return 0;
}