洛谷 小白逛公园 线段树 最大子序列 发表于 2019-08-19 | 分类于 ACM题解 | 阅读次数: 以前的普通做法是O(N^3)做法,同时也不会更新,这里用了线段树 + 单点更新。 题目链接 思路用线段树维护一个子序列,同时进行更新。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117#include <set>#include <map>#include <ctime>#include <queue>#include <cmath>#include <stack>#include <bitset>#include <vector>#include <cstdio>#include <sstream>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>#define eps 1e-8#define lc k * 2#define rc k * 2 + 1#define pi acos(-1.0)#define ll long long#define ull unsigned long longusing namespace std;const int inf = 0x3f3f3f3f;const int maxn = 500005;struct Node{ int sum, max_sum, max_post, max_pre;}tree[maxn * 4];int a[maxn];void pushup(int node){ int ls = node << 1; int rs = node << 1|1; tree[node].sum = tree[ls].sum + tree[rs].sum; tree[node].max_post = max(tree[rs].max_post, tree[ls].max_post + tree[rs].sum); tree[node].max_pre = max(tree[ls].max_pre, tree[ls].sum + tree[rs].max_pre); tree[node].max_sum = max(tree[ls].max_sum, max(tree[rs].max_sum, tree[ls].max_post + tree[rs].max_pre));}void build(int node, int l, int r){ if(l == r) { tree[node].max_post = tree[node].max_pre = a[l]; tree[node].max_sum = tree[node].sum = a[l]; return; } int mid = (l + r) >> 1; build(node << 1, l, mid); build(node << 1|1, mid + 1, r); pushup(node);}void update(int node, int l, int r, int pos, int k){ if(l == r && l == pos) { tree[node].max_post = tree[node].max_pre = tree[node].max_sum = tree[node].sum = k; return; } int mid = (l + r) >> 1; if(pos <= mid) update(node << 1, l, mid, pos, k); else update(node << 1|1, mid + 1, r, pos, k); pushup(node);}Node query(int node, int l, int r, int ql, int qr){ if(ql <= l && qr >= r) { return tree[node]; } int mid = (l + r) >> 1; if(qr <= mid) return query(node << 1, l, mid, ql, qr); else if(ql > mid) return query(node <<1|1, mid + 1, r, ql, qr); else { Node ans, ls, rs; ls = query(node << 1, l, mid, ql, qr); rs = query(node <<1|1, mid + 1, r, ql, qr); ans.sum = ls.sum + rs.sum; ans.max_post = max(rs.max_post, ls.max_post + rs.sum); ans.max_pre = max(ls.max_pre, ls.sum + rs.max_pre); ans.max_sum = max(ls.max_sum, max(rs.max_sum, ls.max_post + rs.max_pre)); return ans; }}int main(){ int n, m, k, p, s; scanf("%d %d",&n,&m); for(int i = 1; i <= n; ++i) scanf("%d",&a[i]); build(1, 1, n); for(int i = 1; i <= m; ++i) { scanf("%d%d%d",&k,&p,&s); if(k == 1) { if(p > s) swap(p,s); Node ans = query(1, 1, n, p, s); cout << ans.max_sum << '\n'; } else { update(1,1,n, p, s); } }} 打赏