题解 SP1716 【GSS3 - Can you answer these queries III】

\[Preface
\]

没有 Preface。

\[Description
\]

维护一个长度为 \(n\) 的数列 \(A\) ，需要支持以下操作：

0 x y 将 \(A_x\) 改为 \(y\) 。
1 x y 求 \(\max\limits_{x \leq l \leq r \leq y}{\sum_{i=l}^rA[i]}\) 。

\[Solution
\]

区间最大子段和 是一个非常经典的问题。

对于 整体最大子段和 来说，一般有 \(O(n)\) 的贪心和分治做法，我们讨论的重点是分治做法。

\(~\)

假设当前需求解最大子段和的区间是 \([l,r]\) ，令 \(mid=\left\lfloor\dfrac{l+r}{2}\right\rfloor\)

我们套路地把 \([l,r]\) 分成 \([l,mid]\) 和 \([mid+1,r]\) ，来进行分治求解：

\(~\)

首先对于形如 \([l,l]\) 的区间，就十分好处理了，这里不多说。

\(~\)

接下来，考虑下最大子段和满不满足 区间可加性 ?（\([l,mid]\) 和 \([mid+1,r]\) 的最大子段和能否推至 \([l,r]\)）

显然，只维护一个最大子段和，对 左子区间 和 右子区间 的最大子段和取个 \(\max\) 是不能维护最大子段和的，因为其漏掉了 最大子段和同时包含左子区间和右子区间 的情况。

那么对于剩下的这一种情况，它是必定经过中点 \(mid\) 的，那这种情况的最大段就是 左子区间从右端点向左走的最大段 与 右子区间从左端点向右走的最大段 的并集，其值为 左子区间的后缀最大子段和 \(+\) 右子区间的前缀最大字段和 。

那我们再维护 前 \(/\) 后缀最大子段和 ，对其三者取 \(\max\) ，最大子段和就满足区间可加性了。

维护 前 \(/\) 后缀最大子段和 依旧可以分成 经过 \(mid\) \(/\) 不经过 \(mid\) 来讨论。

以前缀最大子段和为例，若经过 \(mid\) ，则最大段为 左子区间 与 右子区间从左端点向右走的最大段 的并集，其值为 左子区间和 \(+\) 右子区间的前缀最大子段和 ；若不经过 \(mid\) ，则最大段为 左子区间从左端点向右走的最大段 。二者取个 \(\max\) 即可。后缀最大子段和同理。

那我们再维护个 区间和 ，那 最大子段和 ，前 \(/\) 后缀最大子段和 就都满足区间可加性了。

至于 区间和 \(......\) ，这玩意直接加就行了。

（上述内容大家可以自己画图感性理解一下

\(~\)

求解过程

约定变量：

\(sum\) : 区间和

\(lmax\) : 区间前缀最大子段和

\(rmax\) : 区间后缀最大子段和

\(wmax\) : 区间最大子段和

设函数 \(ask(l,r)\) 求的是关于区间 \([l,r]\) 的一个四元组\((\) \(sum\), \(lmax\), \(rmax\), \(wmax\) \()\)

首先有一个递归边界 \(l=r\) ，此时这四个元素均为 \(A_l\) 。

那对于一般情况，令 \(lc=ask(l,mid),rc=ask(mid+1,r)\) ，则有：

\[self.sum=lc.sum+rc.sum
\]

\[self.lmax=\max(lc.lmax,lc.sum+rc.lmax)
\]

\[self.rmax=\max(rc.rmax,rc.sum+lc.rmax)
\]

\[self.wmax=\max(lc.wmax,rc.wmax,lc.rmax+rc.lmax)
\]

此时 \(self\) 即为 \(ask(l,r)\) 。

struct data{

	int sum;

	int lmax;

	int rmax;

	int wmax;

};

data ask(int l,int r)

{

	data self;

	if(l==r)

	{

		self.sum=self.lmax=self.rmax=self.wmax=A[l];

		return self;

	}

	int mid=(l+r)/2;

	data lc=ask(l,mid),rc=ask(mid+1,r);

	self.sum=lc.sum+rc.sum;

	self.lmax=max(lc.lmax,lc.sum+rc.lmax);

	self.rmax=max(rc.rmax,rc.sum+lc.rmax);

	self.wmax=max(max(lc.wmax,rc.wmax),lc.rmax+rc.lmax);

	return self;

}

\(~\)

然后你会发现，若对于每个询问都调用一次 ask(l,r) 会稳稳 T 掉

那我 bb 这么多有什么用呢

大家仔细想想，这个分治的过程像不像某个数据结构呢？

线段树？

线段树！

是的，用线段树维护，每个节点保存的是该节点所代表的区间 \([l,r]\) 的 \((\) \(sum\), \(lmax\), \(rmax\), \(wmax\) \()\) 。

剩下的都是一些线段树基本操作了。

\[Code
\]

#include<cstdio>

#include<algorithm> 

#define RI register int

using namespace std;

const int SIZE=500100;

int n,m;

int a[SIZE];

struct SegmentTree{

	int l,r;

	int sum;

	int lmax;

	int rmax;

	int dat;

}t[SIZE*4];

void build(int p,int l,int r)

{

	t[p].l=l;t[p].r=r;

	if(l==r){t[p].sum=t[p].lmax=t[p].rmax=t[p].dat=a[l];return;}

	int mid=(l+r)/2;

	build(p*2,l,mid);

	build(p*2+1,mid+1,r);

	t[p].sum=t[p*2].sum+t[p*2+1].sum;

	t[p].lmax=max(t[p*2].lmax,t[p*2].sum+t[p*2+1].lmax);

	t[p].rmax=max(t[p*2+1].rmax,t[p*2+1].sum+t[p*2].rmax);

	t[p].dat=max(max(t[p*2].dat,t[p*2+1].dat),t[p*2].rmax+t[p*2+1].lmax);

}

void change(int p,int x,int val)

{

	if(t[p].l==t[p].r){t[p].sum=t[p].lmax=t[p].rmax=t[p].dat=val;return;}

	int mid=(t[p].l+t[p].r)/2;

	if(x<=mid)change(p*2,x,val);

	else change(p*2+1,x,val);

	t[p].sum=t[p*2].sum+t[p*2+1].sum;

	t[p].lmax=max(t[p*2].lmax,t[p*2].sum+t[p*2+1].lmax);

	t[p].rmax=max(t[p*2+1].rmax,t[p*2+1].sum+t[p*2].rmax);

	t[p].dat=max(max(t[p*2].dat,t[p*2+1].dat),t[p*2].rmax+t[p*2+1].lmax);

}

SegmentTree ask(int p,int l,int r)

{

	if(l<=t[p].l&&t[p].r<=r)return t[p];

	int mid=(t[p].l+t[p].r)/2;

	if(l<=mid&&mid<r)

	{

		SegmentTree lc=ask(p*2,l,r),rc=ask(p*2+1,l,r),self;

		self.sum=self.lmax=self.rmax=self.dat=0;

		self.sum=lc.sum+rc.sum;

		self.lmax=max(lc.lmax,lc.sum+rc.lmax);

		self.rmax=max(rc.rmax,rc.sum+lc.rmax);

		self.dat=max(max(lc.dat,rc.dat),lc.rmax+rc.lmax);

		return self;

	}

	if(l<=mid)

		return ask(p*2,l,r);

	if(mid<r)

		return ask(p*2+1,l,r);

}

int main()

{

	scanf("%d",&n);

	for(RI i=1;i<=n;i++)

		scanf("%d",&a[i]);

	build(1,1,n);

	scanf("%d",&m);

	while(m--)

	{

		char op[2];

		int l,r;

		scanf("%s%d%d",op,&l,&r);

		switch(op[0])

		{

			case '1':{

				if(l>r)swap(l,r);

				printf("%d\n",ask(1,l,r).dat);

				break;

			}

			case '0':{

				change(1,l,r);

				break;

			}

		}

	}

	return 0;

}

\[Thanks \ for \ watching
\]

巴特西

题解 SP1716 【GSS3 - Can you answer these queries III】

最新文章

热门文章