给定长度为N的数列A，以及M条指令，每条指令可能是以下两种之一：
1、“1 x y”，查询区间 [x,y] 中的最大连续子段和，即 maxx≤l≤r≤ymaxx≤l≤r≤y{∑ri=lA[i]∑i=lrA[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≤100000N≤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 #define eps 1e-9 const int inf = 0x3f3f3f3f; const int mod = 1e9+7; const int maxn = 500000 + 8; int n, m, k, x, y; ll a[maxn]; struct node { int l, r; ll sum, dat, lmax, rmax; }tree[4 * maxn]; void push_down(int i) { tree[i].sum = tree[i * 2].sum + tree[i * 2 + 1].sum; tree[i].lmax = max(tree[i * 2].lmax, tree[i * 2].sum + tree[i * 2 + 1].lmax);///紧靠左端的最大连续子段和 tree[i].rmax = max(tree[i * 2 + 1].rmax, tree[i * 2 + 1].sum + tree[i * 2].rmax);///紧靠右端的最大连续子段和 tree[i].dat = max(tree[i * 2].dat, max(tree[i * 2 + 1].dat, tree[i * 2].rmax + tree[i * 2 + 1].lmax));///区间连续最大字段和 } void build(int i, int l, int r) { tree[i].l = l; tree[i].r = r; if(l == r) { tree[i].sum = a[l]; tree[i].dat = a[l]; tree[i].lmax = a[l]; tree[i].rmax = a[l]; return; } int mid = (l + r) / 2; build(i * 2, l, mid); build(i * 2 + 1, mid + 1, r); push_down(i); } void change(int i, int pos, int k) { if(tree[i].l == tree[i].r) { tree[i].sum = k; tree[i].sum = k; tree[i].dat = k; tree[i].lmax = k; tree[i].rmax = k; return; } int mid = (tree[i].l + tree[i].r) / 2; if(pos <= mid) change(i * 2, pos, k); else change(i * 2 + 1, pos, k); push_down(i); } node tmp; node search(int i, int l, int r) { if(tree[i].l >= l && tree[i].r <= r) { return tree[i]; } node a, b, c; a.dat = a.lmax = a.rmax = a.sum = -inf;///左儿子 b.dat = b.lmax = b.rmax = b.sum = -inf;///右儿子 c.dat = c.lmax = c.rmax = -inf;///父节点 c.sum = 0; int mid = (tree[i].l + tree[i].r) / 2; if(l <= mid && r <= mid) { a = search(i * 2, l, r); c.sum += a.sum; } else if(mid < r && mid < l) { b = search(i * 2 + 1, l, r); c.sum += b.sum; } else { a = search(i * 2, l, r); b = search(i * 2 + 1, l, r); c.sum += a.sum + b.sum; } c.dat = max(c.dat, max(a.rmax + b.lmax, max(a.dat, b.dat)));///区间连续最大字段和 c.lmax = max(c.lmax, max(a.lmax, a.sum + b.lmax));///紧靠左端的最大连续子段和 c.rmax = max(c.rmax, max(b.rmax, b.sum + a.rmax));///紧靠右端的最大连续子段和 return c; } int main() { std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m; for(int i = 1; i <= n; i++) cin>>a[i]; build(1, 1, n); for(int i = 0; i < m; i++) { cin>>k>>x>>y; if(k == 1) { if(x > y) swap(x, y); cout<<search(1, x, y).dat<<‘\n‘; } else if(k == 2) { a[x] = y; change(1, x, y); } } return 0; }