區(qū)間最大子段和模板題。。

維護四個數(shù)組：prefix, suffix, sum, tree

假設(shè)當(dāng)前訪問節(jié)點為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差不多，需要返回一個節(jié)點

// luogu-judger-enable-o2 #include <bits/stdc++.h> #define INF 0x3f3f3f3f using 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<typename T> inline T max(T x, T y, T z){ return max(max(x, y), z); } template<typename T> inline T min(T x, T y, T z){ return min(min(x, y), z); } template<typename A, typename B, typename C> 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; }

轉(zhuǎn)載于:https://www.cnblogs.com/onionQAQ/p/10507383.html

總結(jié)

以上是生活随笔為你收集整理的洛谷P4513 小白逛公园的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。