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

￡神魔★判官ぃ 2021-12-17 03:05 123阅读 0赞

## 题意： ##

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

[https_www.cnblogs.com_shl-blog_p_10920913.html]: https://www.cnblogs.com/shl-blog/p/10920913.html