vijos p1083 小白逛公园(单点修改线段树)

描述

小新经常陪小白去公园玩，也就是所谓的遛狗啦…在小新家附近有一条“公园路”，路的一边从南到北依次排着n个公园，小白早就看花了眼，自己也不清楚该去哪些公园玩了。

一开始，小白就根据公园的风景给每个公园打了分-.-。小新为了省事，每次遛狗的时候都会事先规定一个范围，小白只可以选择第a个和第b个公园之间（包括a、b两个公园）选择连续的一些公园玩。小白当然希望选出的公园的分数总和尽量高咯。同时，由于一些公园的景观会有所改变，所以，小白的打分也可能会有一些变化。

那么，就请你来帮小白选择公园吧。

格式

输入格式

第一行，两个整数N和M，分别表示表示公园的数量和操作（遛狗或者改变打分）总数。

接下来N行，每行一个整数，依次给出小白开始时对公园的打分。

接下来M行，每行三个整数。第一个整数K，1或2。K=1表示，小新要带小白出去玩，接下来的两个整数a和b给出了选择公园的范围（1≤a,b≤N， a可以大于b！）；K=2表示，小白改变了对某个公园的打分，接下来的两个整数p和s，表示小白对第p个公园的打分变成了s（1≤p≤N）。

其中，1≤N≤500 000，1≤M≤100 000，所有打分都是绝对值不超过1000的整数。

输出格式

小白每出去玩一次，都对应输出一行，只包含一个整数，表示小白可以选出的公园得分和的最大值。

样例1

样例输入1

5 3
1 2 -3 4 5
1 2 3
2 2 -1
1 2 3

样例输出1

2
-1

这道题要用线段树维护区间最大连续字段和。
想想 pushup 的时候，我们怎么得到最大连续字段和？

由图，区间最大连续子段和可能来自橙色部分，绿色部分和蓝色部分。
橙色和蓝色部分来自子区间的最大连续字段和，很好办。
但是跨越了中间点m的绿色部分怎么得到呢？
其实绿色部分即是左区间的最大后缀和+右区间的最大前缀和，这样一来，我们在pushup的时候就要维护一个区间的最大子段和，最大前缀和和最大后缀和。
再想想最大前缀和和最大后缀和怎么得到？
我们来看看最大后缀和的两种情况：
①：

这种情况下，区间的最大后缀和 = 左区间的最大后缀和 + 右区间的总和

②：

这种情况下，区间的最大后缀和 = 右区间的最大后缀和
区间最大前缀和可以同理得到。
我们发现，维护前缀和和后缀和，需要维护一个sum，即是区间总和。
于是我们发现了一个节点需要维护的四个值：
sum（总和）, maxsum（最大子段和）, prefix（最大前缀和）和 suffix（最大后缀和）

值得一提的是

在询问的时候，我们应该返回一个结构体而不是一个值，这个结构体应具有四个值的全部信息。

下面是代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define LL long long
#define N 500003
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
struct node{
	int ms, suf, pre, s;
}d[N * 4];
void pushup(int rt){
	d[rt].s = d[rt<<1].s + d[rt<<1|1].s;
	d[rt].ms = max(d[rt<<1].ms, max(d[rt<<1|1].ms, d[rt<<1].suf + d[rt<<1|1].pre));
	d[rt].pre = max(d[rt<<1].pre, d[rt<<1].s + d[rt<<1|1].pre);
	d[rt].suf = max(d[rt<<1|1].suf, d[rt<<1].suf + d[rt<<1|1].s);
}
void build(int l, int r, int rt){
	if(l == r){
		scanf("%d", &d[rt].s);
		d[rt].ms = d[rt].pre = d[rt].suf = d[rt].s;
		return;
	}
	int m = l + r >> 1;
	build(lson);
	build(rson);
	pushup(rt);
}
void update(int l, int r, int rt, int p, int c){
	if(l == r){
		d[rt].s = d[rt].ms = d[rt].pre = d[rt].suf = c;
		return;
	}
	int m = l + r >> 1;
	if(p <= m) update(lson, p, c);
	else update(rson, p, c);
	pushup(rt);
}
node query(int l, int r, int rt, int a, int b){
	
	if(l >= a && r <= b) return d[rt];
	int m = l + r >> 1, max1;
	node s1, s2;
	if(b <= m) return query(lson, a, b);
	else if(a > m) return query(rson, a, b);
	else{
		node ans1, ans2, ans3;
		ans1 = query(lson, a, m);
		ans2 = query(rson, m+1, b);
		ans3.s = ans1.s + ans2.s;
		ans3.pre = max(ans1.pre, ans1.s + ans2.pre);
		ans3.suf = max(ans2.suf, ans1.suf + ans2.s);
		ans3.ms = max(ans1.ms, max(ans2.ms, ans1.suf + ans2.pre));
		return ans3;
	}
}
int main(){
	int i, j, n, m, o, a, b, c;
	scanf("%d%d", &n, &m);
	build(1, n, 1);
	for(i = 1; i <= m; i++){
		scanf("%d%d%d", &o, &a, &b);
		if(o == 1){
			if(a > b) swap(a, b);
			printf("%d\n", query(1, n, 1, a, b).ms);
		}
		else update(1, n, 1, a, b);
	}
	return 0;
}

各种题解及学习笔记~ 文章被收录于专栏

各种题解及学习笔记