【题解】小白逛公园

标签 : 线段树

题目大意

给定一个区间，两种操作：

操作1： 查询区间内最大子段和

操作2： 单点修改。

解析

暴力查询区间最大子段和时间复杂度是 $ O(n) $ 的，一定会爆炸。观察数据范围，正解的时间复杂度大约是 \(log\) 级别的。再根据单点修改，可以尝试一下线段树。

单点修改好做，关键在于区间查询最大子段和。主要工作在于线段树的合并。

我们每个节点维护四个值，一个是最大前缀和，一个是最大后缀和，一个是区间和，一个是区间答案。

我们分步考虑每种情况。

1.前缀和： 两种情况，一种是左子树的最大前缀和作为该节点的最大前缀和，另一种是左子树的区间和加上右子树的最大前缀和，比较即可。

2.后缀和： 和上面的差不多。

3.区间答案： 三种情况，一种是左子树的答案，一种是右子树的答案，一种是左子树的最大后缀与右子树的最大前缀的和，三者比较一下。

以上操作就是 \(pushup\) 的内容。

一点小细节

1. 查询的时候也要进行一次类似于pushup的操作。

2. 小心输入的区间 \(l>r\) (bushi.

code

#include
#include
#define Maxn 1200000
using namespace std;
typedef long long ll;
ll n,m,a[Maxn];
struct Tree {
	ll l,r,ans,sum;
	ll ansl,ansr;
}tree[Maxn<<4];
void pushup(int i) {
	tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;
	tree[i].ansl=max(tree[i<<1].ansl,tree[i<<1].sum+tree[i<<1|1].ansl);
	tree[i].ansr=max(tree[i<<1|1].ansr,tree[i<<1|1].sum+tree[i<<1].ansr);
	tree[i].ans=max(max(tree[i<<1].ans,tree[i<<1|1].ans),tree[i<<1].ansr+tree[i<<1|1].ansl);
	return ;
}
void build(ll i,ll l,ll r) {
	tree[i].l=l,tree[i].r=r;
	if(l==r) {
		tree[i].sum=a[l];
		tree[i].ans=a[l];
		tree[i].ansl=a[l];
		tree[i].ansr=a[l];
		return ;
	}
	ll mid=(l+r)>>1;
	build(i<<1,l,mid);
	build(i<<1|1,mid+1,r);
	pushup(i);
}
Tree search(ll i,ll l,ll r){
	Tree res;
	if(l<=tree[i].l&&tree[i].r<=r) {
		return tree[i];
	}
	ll mid=(tree[i].l+tree[i].r)>>1;
	if(r<=mid) {
		return search(i<<1,l,r);
	}else if(l>mid){
		return search(i<<1|1,l,r);
	}else{
		Tree temp1=search(i<<1,l,r),	temp2=search(i<<1|1,l,r);
		res.sum=temp1.sum+temp2.sum;
		res.ansl=max(temp1.ansl,temp1.sum+temp2.ansl);
		res.ansr=max(temp2.ansr,temp2.sum+temp1.ansr);
		res.ans=max(max(temp1.ans,temp2.ans),temp1.ansr+temp2.ansl);
		return res;
	}
}
void change(ll i,ll pos,ll x) {
	if(tree[i].l==tree[i].r) {
	//	printf("%d",tree[i].l);
		tree[i].sum=x;
		tree[i].ans=x;
		tree[i].ansl=x;
		tree[i].ansr=x;
		return ;
	}
	ll mid=(tree[i].l+tree[i].r)>>1;
	if(pos<=mid) change(i<<1,pos,x);
	else change(i<<1|1,pos,x);
	pushup(i);
}
//void check(int i) {
//	printf("i；%d l；%lld r:%lld\n",i,tree[i].l,tree[i].r);
//	printf("sum:%lld ",tree[i].sum);
//	printf("ans:%lld ",tree[i].ans);
//	printf("ansl:%lld ",tree[i].ansl);
//	printf("ansr:%lld\n",tree[i].ansr);
//	if(tree[i].l==tree[i].r) return;
//	check(i<<1),check(i<<1|1);
//}
int main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++) {
		scanf("%lld",&a[i]);
	}
	build(1,1,n);
	while(m--) {
		int ty;
		scanf("%d",&ty);
		if(ty==1) {
			int l,r;
			scanf("%d%d",&l,&r);
			if(l>r) swap(l,r);
			Tree res=search(1,l,r);
			printf("%lld\n",res.ans);
		}else {
			ll pos,x;
			scanf("%lld%lld",&pos,&x);
			change(1,pos,x);
		}
	}
	return 0;
}