区间最大子段和模板题。。
维护四个数组：prefix, suffix, sum, tree
假设当前访问节点为cur
- prefix[cur]=max(prefix[lson],sum[lson]+preifx[rson])
- suffix[cur]=max(suffix[rson],sum[rson]+suffix[lson])
- sum[cur]=sum[lson]+sum[rson]
- tree[cur]=max(tree[lson], tree[rson], suffix[lson]+suffix[rson])
在query的时候要注意合并，其实和pushup差不多，需要返回一个节点
// luogu-judger-enable-o2#include#define INF 0x3f3f3f3fusing namespace std;typedef long long ll;inline int lowbit(int x){ return x & (-x); }inline int read(){ int X = 0, w = 0; char ch = 0; while(!isdigit(ch)) { w |= ch == '-'; ch = getchar(); } while(isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar(); return w ? -X : X;}inline int gcd(int a, int b){ return a % b ? gcd(b, a % b) : b; }inline int lcm(int a, int b){ return a / gcd(a, b) * b; }template inline T max(T x, T y, T z){ return max(max(x, y), z); }template inline T min(T x, T y, T z){ return min(min(x, y), z); }template inline A fpow(A x, B p, C yql){ A ans = 1; for(; p; p >>= 1, x = 1LL * x * x % yql)if(p & 1)ans = 1LL * x * ans % yql; return ans;}const int N = 500005;struct Node{ int prefix, suffix, tree, sum; Node(int p, int s, int t, int u): prefix(p), suffix(s), tree(t), sum(u){}};int n, m, a[N];int prefix[N<<2], suffix[N<<2], sum[N<<2], tree[N<<2];void push_up(int treeIndex){ int lson = treeIndex << 1, rson = treeIndex << 1 | 1; prefix[treeIndex] = max(prefix[lson], sum[lson] + prefix[rson]); suffix[treeIndex] = max(suffix[rson], sum[rson] + suffix[lson]); sum[treeIndex] = sum[lson] + sum[rson]; tree[treeIndex] = max(tree[lson], tree[rson], suffix[lson] + prefix[rson]);}void buildTree(int treeIndex, int l, int r){ if(l == r){ tree[treeIndex] = prefix[treeIndex] = suffix[treeIndex] = sum[treeIndex] = a[l]; return; } int mid = (l + r) >> 1; buildTree(treeIndex << 1, l, mid); buildTree(treeIndex << 1 | 1, mid + 1, r); push_up(treeIndex);}void modify(int treeIndex, int l, int r, int k, int e){ if(l == r){ tree[treeIndex] = prefix[treeIndex] = suffix[treeIndex] = sum[treeIndex] = e; return; } int mid = (l + r) >> 1; if(k <= mid) modify(treeIndex << 1, l, mid, k, e); else modify(treeIndex << 1 | 1, mid + 1, r, k, e); push_up(treeIndex);}Node query(int treeIndex, int l, int r, int queryL, int queryR){ if(l == queryL && r == queryR){ return Node(prefix[treeIndex], suffix[treeIndex], tree[treeIndex], sum[treeIndex]); } int mid = (l + r) >> 1; if(queryL > mid) return query(treeIndex << 1 | 1, mid + 1, r, queryL, queryR); else if(queryR <= mid) return query(treeIndex << 1, l, mid, queryL, queryR); Node lr = query(treeIndex << 1, l, mid, queryL, mid); Node rr = query(treeIndex << 1 | 1, mid + 1, r, mid + 1, queryR); Node ret = Node(max(lr.prefix, lr.sum + rr.prefix), max(rr.suffix, rr.sum + lr.suffix), max(lr.tree, rr.tree, lr.suffix + rr.prefix), lr.sum + rr.sum); return ret;}int main(){ n = read(), m = read(); for(int i = 1; i <= n; i ++) a[i] = read(); buildTree(1, 1, n); while(m --){ int opt = read(), p = read(), q = read(); if(opt == 1){ if(p > q) swap(p, q); printf("%d\n", query(1, 1, n, p, q).tree); } else if(opt == 2){ modify(1, 1, n, p, q); } } return 0;}