SP1716 GSS3 - Can you answer these queries III

博主： tony102
发布时间：2020 年 10 月 12 日
1903 次浏览
暂无评论
851字数
分类：题解

[Link](https://www.luogu.com.cn/problem/SP1716)

## Sol

有一点意思的一道线段树题

最大子段和问题在基础的dp里应该大家都有见识，但是一个带修的多组询问区间最大子段和还是不一样

试着考虑一个最大子段和会如何构成

假如$p$维护的是$[l,r]$内的最大子段和，其左右儿子分别为$lson$ 、$rson$

那么$p$的最大子段和有三种情况组成

1. 是$lson$的最大子段和
2. 是$rson$的最大子段和
3. 由$lson$的一段后缀(suffix)和$rson$的一段前缀(prefix)拼在一起组成

此时我们的思路很清楚了，我们维护区间的最大前缀和($pre$)，最大后缀和($suf$)，整个区间的和($sum$)，和区间最大子段和($w$)

最大前缀和可以由当前节点$p$的左儿子的$pre$转移而来，也可以是整个左儿子区间+右儿子的$pre$组成

最大后缀和可以有当前节点$p$的右儿子的$suf$转移而来，也可以是整个右儿子区间+左儿子的$suf$组成

## Summary

这道题带给我们最大的启发就是，线段树可以维护的信息一定是满足**结合律**的，所以我们在解决线段树的问题时不妨把不容易维护的信息转化成一些可以结合的信息，再通过这些信息的组合得到我们要的答案

## Code

```c++
#include <bits/stdc++.h>
using namespace std;

const int SIZE = 5e5 + 5;

int n, m;
int a[SIZE];

struct node {
	int suf, pre, sum, p, l, r;
} tree[SIZE << 2];

inline int read()
{
	char ch = getchar();
	int f = 1, x = 0;
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
	return x * f;
}

#define lson(p) p << 1
#define rson(p) p << 1 | 1

inline void pushUp(int p)
{
	tree[p].sum = tree[lson(p)].sum + tree[rson(p)].sum;
	tree[p].pre = std::max(tree[lson(p)].pre, tree[lson(p)].sum + tree[rson(p)].pre);
	tree[p].suf = std::max(tree[rson(p)].suf, tree[rson(p)].sum + tree[lson(p)].suf);
	tree[p].p = std::max(std::max(tree[lson(p)].p, tree[rson(p)].p), tree[lson(p)].suf + tree[rson(p)].pre);
}

inline void build(int p, int l, int r)
{
	tree[p].l = l, tree[p].r = r;
	if (l == r) {
		tree[p].sum = tree[p].suf = tree[p].pre = tree[p].p = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(lson(p), l, mid); build(rson(p), mid + 1, r);
	pushUp(p);
}

inline void modify(int p, int pos, int val)
{
	if (tree[p].l == pos && tree[p].r == pos) {
		tree[p].sum = tree[p].suf = tree[p].pre = tree[p].p = val;
		return;
	}
	int mid = (tree[p].l + tree[p].r) >> 1;
	if (pos <= mid) modify(lson(p), pos, val);
	else modify(rson(p), pos, val);
	pushUp(p);
}

inline node query(int p, int l, int r)
{
	if (l <= tree[p].l && tree[p].r <= r) {
		return tree[p];
	}
	int mid = (tree[p].l + tree[p].r) >> 1;
	node ans;
	if (r <= mid) ans = query(lson(p), l, r);
	else if (l > mid) ans = query(rson(p), l, r);
	else {
		node leftAns = query(lson(p), l, r), rightAns = query(rson(p), l, r);
		ans.sum = leftAns.sum + rightAns.sum;
		ans.pre = std::max(leftAns.pre, leftAns.sum + rightAns.pre);
		ans.suf = std::max(rightAns.suf, rightAns.sum + leftAns.suf);
		ans.p = std::max(std::max(leftAns.p, rightAns.p), leftAns.suf + rightAns.pre);
	}
	return ans;
}

int main()
{
	n = read();
	for (int i = 1; i <= n; ++ i) a[i] = read();
	build(1, 1, n);
	int opt = 0, a, b;
	m = read();
	while (m --) {
		opt = read();
		if (opt == 1) {
			a = read(), b = read();
			if (a > b) std::swap(a, b);
			printf("%d\n", query(1, a, b).p);
		}
		if (opt == 0) {
			a = read(), b = read();
			modify(1, a, b);
		}
	}
	return 0;
}
```

最后修改：2021 年 09 月 04 日