描述
给定长度为N的数列A，以及M条指令 (N≤500000, M≤100000)，每条指令可能是以下两种之一：
“2 x y”，把 A[x] 改成 y。
“1 x y”，查询区间 [x,y] 中的最大连续子段和，即 max(x≤l≤r≤y)? { ∑(i=l~r) A[i] }。
对于每个询问，输出一个整数表示答案。
输入格式
第一行两个整数N,M
第二行N个整数Ai
接下来M行每行3个整数k,x,y，k=1表示查询（此时如果x>y，请交换x,y），k=2表示修改
输出格式
对于每个询问输出一个整数表示答案。
样例输入
5 3 1 2 -3 4 5 1 2 3 2 2 -1 1 3 2
样例输出
2 -1
数据范围与约定
- 对于100%的数据: N≤500000, M≤100000, |Ai|<=1000
题解：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define INF -0x3f3f3f3f
#define ll long long
using namespace std;
const int maxn = 500010;
int n, m;
int a[maxn];
struct SegmentTree{int l, r;int dat, sum, lmax, rmax;
}t[maxn<<2];
void init(SegmentTree &tree, int x){tree.dat=tree.lmax=tree.rmax=tree.sum=x;
}
void push_up(int p){t[p].sum = t[2*p].sum + t[2*p+1].sum;t[p].lmax = max(t[2*p].lmax, t[2*p].sum+t[2*p+1].lmax);t[p].rmax = max(t[2*p+1].rmax, t[2*p+1].sum+t[2*p].rmax);t[p].dat = max(t[2*p].dat, max(t[2*p+1].dat, t[2*p].rmax+t[2*p+1].lmax));
}
void build(int p, int l, int r){t[p].l = l, t[p].r = r;if(l == r){init(t[p], a[l]);return;}int mid = (l+r)/2;build(2*p, l, mid);build(2*p+1, mid+1, r);push_up(p);
}
void change(int p, int x, int val){if(t[p].l == t[p].r){init(t[p], val);return ;}int mid = (t[p].l+t[p].r)/2;if(x <= mid) change(2*p, x, val);else change(2*p+1, x, val);push_up(p);
}
SegmentTree ask(int p, int l, int r){if(l <= t[p].l && r >= t[p].r){return t[p];}int mid = (t[p].l+t[p].r)/2;SegmentTree a, b, c;init(a, INF), init(b, INF);c.sum = 0;if(l <= mid) {a = ask(2*p, l, r);c.sum += a.sum;}if(r > mid) {b = ask(2*p+1, l, r);c.sum += b.sum;}c.dat = max(max(a.dat, b.dat), a.rmax+b.lmax);c.lmax = max(a.lmax, b.lmax+a.sum);c.rmax = max(b.rmax, a.rmax+b.sum);return c;
}
int main()
{int k, x, y;cin >> n >> m;for(int i = 1; i <= n; i++){cin >> a[i];}build(1,1,n);while(m--){cin >> k >> x >> y;if(k == 1){if(x > y) swap(x, y);printf("%d\n", ask(1,x,y).dat);}else change(1,x,y);}return 0;
}