OI - k-Maximum Subsequence Sum(Codeforces)

开始一轮~~数据结构~~线段树复习……

题目链接：Codeforces 280D

Part1. 题意

给出一个长度为 $n$ 的数列 $a_1,a_2,…,a_n$；有 $m$ 次操作，操作包括下面两种：

0 x y 将 $a_x$ 的值改为 $y$；
1 l r k 在区间 $[l,r]$ 里选择至多 $k$ 个不相交的区间，使得这些区间中的所有数之和最大，求这个最大值（也可以什么区间都不选，答案就是 0）。

数据规模：
$1\le n,m\le10^5$，$-500\le a_i\le500$；
对于操作 1 ：$1\le x\le n$，$-500\le y\le500$；
对于操作 2 ：$1\le l\le r\le n$，$1\le k\le20$；

Part2. 解析

Part2/1. 最大子段和

先考虑如果不存在修改（操作1），只有一次询问：在 $[l,r]$ 中选择至多 $k$ 个区间。

如果 $k=1$，就是一个非常经典的“最大子段和”

Hint. 最大子段和
给定原数列，求一个子区间，使得其中的数之和最大。

可以用线段树维护 ①区间最大子段和 mx[l,r]、②从区间的最左端开始的最大子段和 mxL[l,r]、③从区间的最右端开始的最大子段和 mxR[l,r]、④区间和 sum[l,r]；

//计算 [l,r] 的最大子段和
mx[l,r] = max{ mx[l,m]/*全在左边*/ , mx[m+1,r]/*全在右边*/ , mxR[l,m]+mxL[m+1,r]/*左右区间拼接*/ }

//计算 [l,r] 靠左的最大子段和
mxL[l,r] = max{ mxL[l,m]/*全在左边*/ , sum[l,m]+mxL[m+1,r]/*左右拼接*/ }

//计算 [l,r] 靠右的最大子段和，同上
mxR[l,r] = max{ mxR[m+1,r] , mxR[l,m]+sum[m+1,r] }

//计算区间和
sum[l,r] = sum[l,m]+sum[m+1,r]

这样就可以维护了 ~

Part2/2. 带区间反转的最大子段和

先不要管为什么需要这个操作

考虑操作：将指定区间 $[l,r]$ 内的每个数乘上 $-1$；要求动态维护最大子段和

仍然考虑线段树，首先线段树里就需要反转的懒标记 lzy[l,r] 了。

然后看看当一个区间 $[l,r]$ 反转了，它的 mx[l,r], mxL[l,r], mxR[l,r], sum[l,r] 会怎么变 ——

最简单的就是 sum[l,r] ，直接乘上 $-1$ 就可以了。
mx[l,r], mxL[l,r], mxR[l,r] 的值都会乘上 $-1$；它们原来是最大值，那么乘上 $-1$ 后就变成了对应的最小值……原来的最小值乘上 $-1$ 也就变成了对应的最大值。

突然发现还要维护 ①区间最小子段和 mn[l,r]、②从区间最左端开始的最小子段和 mnL[l,r]、③从区间最右端开始的最小子段和 mnR[l,r]；维护方法一样。

然后反转的操作就是：

swap( mn[l,r] , mx[l,r] )
swap( mnL[l,r] , mxL[l,r] )
swap( mnR[l,r] , mxR[l,r] )

mn[l,r] mx[l,r] mnL[l,r] mxL[l,r] mnR[l,r] mxR[l,r] sum[l,r] *= -1

Part2/3. k次最大子段和

下面这种情况，我们已经求出了一个最大子段和，想要根据这个情况推出选两个区间时的最大子段和：

上图的蓝色块是第一次选择的区间，“第二次选择”有三种方案：

不包括蓝色块的区间：
从蓝色块中选出一段区间断开：
选一段区间与蓝色块相交（不包含），删去中间部分：

这样我们就可以得到两个区间（而且包含了所有情况），发现这两个区间的数之和为“前后两次选取区间的数之和 - 重叠部分的数之和”。

于是就得到一种方案：选取第一个区间后，将该区间反转，再选第二个区间，所以一直做最大子段和就可以了。

然后发现……我们不仅要求出最大子段和是多少，还要求出最大子段和到底是哪一段……所以

Part2/4. 结构体优化

定义一个“区间”结构体

struct NODE{
	int val,Vl,Vr;
	NODE(int _val=0,int _Vl=0,int _Vr=0):val(_val),Vl(_Vl),Vr(_Vr){}
};

val 表示该区间的数之和，Vl,Vr 分别表示区间的左右端点。然后就可以重载运算符了：

//比较两个区间大小，其实就是比较两个区间的元素之和的大小（这样就可以用 max,min 了）
bool operator <(const NODE Pa,const NODE Pb){return Pa.val<Pb.val;}
bool operator >(const NODE Pa,const NODE Pb){return Pa.val>Pb.val;}
//两个相邻区间相连接，注意连接顺序：把Pa和Pb接起来
NODE operator +(const NODE Pa,const NODE Pb){return NODE(Pa.val+Pb.val,Pa.Vl,Pb.Vr);}
//区间整体乘上一个数字 Pb
NODE operator *(const NODE Pa,const int Pb){return NODE(Pa.val*Pb,Pa.Vl,Pa.Vr);}
NODE operator *=(NODE &Pa,const int Pb){Pa.val*=Pb;return Pa;}

我觉得这样打包过后可以简化代码……

Part3. 源代码

/*Lucky_Glass*/
#include<stack>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1e5;

int n,m;
int Ia[N+3];

struct NODE{
	int val,Vl,Vr;
	NODE(int _val=0,int _Vl=0,int _Vr=0):val(_val),Vl(_Vl),Vr(_Vr){}
};
bool operator <(const NODE Pa,const NODE Pb){return Pa.val<Pb.val;}
bool operator >(const NODE Pa,const NODE Pb){return Pa.val>Pb.val;}
NODE operator +(const NODE Pa,const NODE Pb){return NODE(Pa.val+Pb.val,Pa.Vl,Pb.Vr);}
NODE operator *(const NODE Pa,const int Pb){return NODE(Pa.val*Pb,Pa.Vl,Pa.Vr);}
NODE operator *=(NODE &Pa,const int Pb){Pa.val*=Pb;return Pa;}
struct RESULT{
	NODE mid,lef,rig,sum;
	RESULT(NODE _m,NODE _l,NODE _r,NODE _s):mid(_m),lef(_l),rig(_r),sum(_s){}
};
struct SEGTREE{
	NODE Emx[N*4],EmxL[N*4],EmxR[N*4],Emn[N*4],EmnL[N*4],EmnR[N*4],Esum[N*4];
	bool Zrev[N*4];
	void GetRev(int u){
		swap(Emx[u],Emn[u]);swap(EmxL[u],EmnL[u]);swap(EmxR[u],EmnR[u]);
		Emx[u]*=-1;Emn[u]*=-1;EmxL[u]*=-1;EmnL[u]*=-1;EmxR[u]*=-1;EmnR[u]*=-1;
		Esum[u]*=-1;
	}
	void PushUp(int u){
		Emx[u]=max(max(Emx[u<<1],Emx[u<<1|1]),EmxR[u<<1]+EmxL[u<<1|1]);
		Emn[u]=min(min(Emn[u<<1],Emn[u<<1|1]),EmnR[u<<1]+EmnL[u<<1|1]);
		EmxL[u]=max(EmxL[u<<1],Esum[u<<1]+EmxL[u<<1|1]);
		EmnL[u]=min(EmnL[u<<1],Esum[u<<1]+EmnL[u<<1|1]);
		EmxR[u]=max(EmxR[u<<1|1],EmxR[u<<1]+Esum[u<<1|1]);
		EmnR[u]=min(EmnR[u<<1|1],EmnR[u<<1]+Esum[u<<1|1]);
		Esum[u]=Esum[u<<1]+Esum[u<<1|1];
	}
	void PushDown(int u,int Vl,int Vr){
		if(Vl<Vr && Zrev[u]){
			GetRev(u<<1);Zrev[u<<1]=!Zrev[u<<1];
			GetRev(u<<1|1);Zrev[u<<1|1]=!Zrev[u<<1|1];
		}
		Zrev[u]=false;
	}
	void Build(int u,int Vl,int Vr){
		if(Vl==Vr){
			Emn[u]=EmnL[u]=EmnR[u]=Emx[u]=EmxL[u]=EmxR[u]=Esum[u]=NODE(Ia[Vl],Vl,Vl);
			return;
		}
		int Vm=(Vl+Vr)>>1;
		Build(u<<1,Vl,Vm);Build(u<<1|1,Vm+1,Vr);
		PushUp(u);
	}
	void Modify(int u,int Vl,int Vr,int Upos,int Uval){
		if(Vr<Upos || Upos<Vl) return;
		if(Vl==Vr){
			Emn[u]=EmnL[u]=EmnR[u]=Emx[u]=EmxL[u]=EmxR[u]=Esum[u]=NODE(Uval,Upos,Upos);
			return;
		}
		PushDown(u,Vl,Vr);
		int Vm=(Vl+Vr)>>1;
		Modify(u<<1,Vl,Vm,Upos,Uval);Modify(u<<1|1,Vm+1,Vr,Upos,Uval);
		PushUp(u);
	}
	void Reverse(int u,int Vl,int Vr,int Ul,int Ur){
		if(Vr<Ul || Ur<Vl) return;
		if(Ul<=Vl && Vr<=Ur){
			Zrev[u]=!Zrev[u];
			GetRev(u);
			return;
		}
		PushDown(u,Vl,Vr);
		int Vm=(Vl+Vr)>>1;
		Reverse(u<<1,Vl,Vm,Ul,Ur);
		Reverse(u<<1|1,Vm+1,Vr,Ul,Ur);
		PushUp(u);
	}
	RESULT Query(int u,int Vl,int Vr,int Ul,int Ur){
		if(Ul<=Vl && Vr<=Ur) return RESULT(Emx[u],EmxL[u],EmxR[u],Esum[u]);
		PushDown(u,Vl,Vr);
		int Vm=(Vl+Vr)>>1;
		if(Ur<Vm+1) return Query(u<<1,Vl,Vm,Ul,Ur);
		if(Vm<Ul) return Query(u<<1|1,Vm+1,Vr,Ul,Ur);
		RESULT Rl=Query(u<<1,Vl,Vm,Ul,Ur),Rr=Query(u<<1|1,Vm+1,Vr,Ul,Ur);
		return RESULT(max(max(Rl.mid,Rr.mid),Rl.rig+Rr.lef),max(Rl.lef,Rl.sum+Rr.lef),max(Rr.rig,Rl.rig+Rr.sum),Rl.sum+Rr.sum);
	}
}seg;

stack< pair<int,int> > Sclr;
int main(){
//	freopen("output.txt","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&Ia[i]);
	scanf("%d",&m);
	seg.Build(1,1,n);
	while(m--){
		int Iopt;scanf("%d",&Iopt);
		if(Iopt){
			int Il,Ir,Ik,Vans=0;scanf("%d%d%d",&Il,&Ir,&Ik);
			while(Ik--){
				RESULT Rr=seg.Query(1,1,n,Il,Ir);
				NODE fRr=max(Rr.mid,max(Rr.lef,Rr.rig));
				if(fRr.val<0) break;
				Sclr.push(make_pair(fRr.Vl,fRr.Vr));
				Vans+=fRr.val;
				seg.Reverse(1,1,n,fRr.Vl,fRr.Vr);
			}
			printf("%d\n",Vans);
			while(!Sclr.empty()){
				seg.Reverse(1,1,n,Sclr.top().first,Sclr.top().second);
				Sclr.pop();
			}
		}
		else{
			int Ipos,Ival;scanf("%d%d",&Ipos,&Ival);
			seg.Modify(1,1,n,Ipos,Ival);
		}
	}
	return 0;
}

The End

Thanks for reading!

Email: lucky_glass@foxmail.com，欢迎提问！