CH4301 Can youanswer on these queries III （线段树）

本文主要是介绍CH4301 Can youanswer on these queries III （线段树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

给定长度为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] }。

分析：

线段树维护区间最大子段和，本题的关键在于如何维护区间最大子段和。对于线段树的每一个节点，我们定义四域：sum,l,r,maxx分别表示这个区间的和、以这个区间左边为起点的最大子段和是多少、以这个区间右边为起点的最大子段和是多少、这个区间的最大子段和是多少。当我们用这个区间的两个子区间合并他的时候，就会有如下结论：

1. a[now].sum=a[now<<1].sum+a[now<<1|1].sum;

2. a[now].l=max(a[now<<1].l,a[now<<1].sum+a[now<<1|1].l);

3. a[now].r=max(a[now<<1|1].r,a[now<<1|1].sum+a[now<<1].r);

4. a[now].maxx=max(max(a[now<<1].maxx,a[now<<1|1].maxx),a[now<<1].r+a[now<<1|1].l);

有了这个，这道题就容易多了，本题为单点修改，将难度降低了一下，用线段树按照上述步骤处理即可。

参考：https://www.cnblogs.com/shl-blog/p/10920913.html。

LYD代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 500006, INF = 0x3f3f3f3f;
int n, m, a[N];
struct T {int l, r, s, lx, rx, ans;
} t[N*4];void build(int p, int l, int r) {t[p].l = l;t[p].r = r;if (l == r) {t[p].s = t[p].lx = t[p].rx = t[p].ans = a[l];return;}int mid = (l + r) >> 1;build(p << 1, l, mid);build(p << 1 | 1, mid + 1, r);t[p].s = t[p<<1].s + t[p<<1|1].s;t[p].lx = max(t[p<<1].lx, t[p<<1].s + t[p<<1|1].lx);t[p].rx = max(t[p<<1|1].rx, t[p<<1].rx + t[p<<1|1].s);t[p].ans = max(max(t[p<<1].ans, t[p<<1|1].ans), t[p<<1].rx + t[p<<1|1].lx);
}void change(int p, int x, int y) {if (t[p].l == t[p].r) {t[p].s = t[p].lx = t[p].rx = t[p].ans = y;return;}int mid = (t[p].l + t[p].r) >> 1;if (x <= mid) change(p << 1, x, y);else change(p << 1 | 1, x, y);t[p].s = t[p<<1].s + t[p<<1|1].s;t[p].lx = max(t[p<<1].lx, t[p<<1].s + t[p<<1|1].lx);t[p].rx = max(t[p<<1|1].rx, t[p<<1].rx + t[p<<1|1].s);t[p].ans = max(max(t[p<<1].ans, t[p<<1|1].ans), t[p<<1].rx + t[p<<1|1].lx);
}T ask(int p, int l, int r) {if (l <= t[p].l && r >= t[p].r) return t[p];T a, b, ans;a.s = a.lx = a.rx = a.ans = b.s = b.lx = b.rx = b.ans = -INF;ans.s = 0;int mid = (t[p].l + t[p].r) >> 1;if (l <= mid) {a = ask(p << 1, l, r);ans.s += a.s;}if (r > mid) {b = ask(p << 1 | 1, l, r);ans.s += b.s;}ans.ans = max(max(a.ans, b.ans), a.rx + b.lx);ans.lx = max(a.lx, a.s + b.lx);ans.rx = max(b.rx, b.s + a.rx);if (l > mid) ans.lx = max(ans.lx, b.lx);if (r <= mid) ans.rx = max(ans.rx, a.rx);return ans;
}int main() {cin >> n >> m;for (int i = 1; i <= n; i++) scanf("%d", &a[i]);build(1, 1, n);while (m--) {int t, x, y;scanf("%d %d %d", &t, &x, &y);if (t == 1) {if (x > y) swap(x, y);cout << ask(1, x, y).ans << endl;}else change(1, x, y);}return 0;
}

 

 

这篇关于CH4301 Can youanswer on these queries III （线段树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---