自动搬运

查看原文

来自洛谷，原作者为

	cyffff Not yet for the story on the last page, it's not the end.

搬运于2025-08-24 22:44:00，当前版本为作者最后更新于2023-01-15 19:34:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$\text{Link}$

第一次 $\text{AK div.2}$，水个题解不过分吧（

题意

给一个仅包含 $-1,0,1$ 的序列 $a$。在为 $0$ 的位置中选 $k$ 个更改为 $1$，其余更改为 $-1$，使得最大子段和最大，求最大子段和的最大值。

$k\le n\le 10^7$。

思路

看数据范围像几个前缀和就做完了。

枚举左端点减一，设为 $i$。考虑右端点 $j$。

记原序列前缀和为 $pr_i$。

我们考虑定义 $c$ 表示 $[i,j]$ 中 $0$ 的数量。我们肯定尽可能填 $1$，再填 $-1$，则对 $c$ 的大小分类讨论：

• $c\le k$，这段的子段和为 $pr_j-pr_i+c$；
• $c>k$，这段的子段和为 $pr_j-pr_i+2k-c$。

我们定义 $pos_i$ 为第 $i$ 个 $0$ 的位置，$l_i$ 为 $i$ 左方（不含 $i$）的最后一个 $0$ 是第几个 $0$。则当 $j\in(i,pos_{l_i+k+1})$ 时 $c\le k$，$j\in[pos_{l_i+k+1},n]$ 时 $c>k$。

考虑将 $c$ 从式子中消掉。我们定义 $p_{-1,i}$ 表示将 $0$ 全部换为 $-1$ 后的前缀和，$p_{1,i}$ 表示将 $0$ 全部换为 $1$ 后的前缀和。则两种情况的答案分别变成了$p_{1,j}-p_{1,i}$ 和 $p_{-1,j}-p_{-1,i}+2k$。

对于后者，我们直接维护 $p_{-1,i}$ 的后缀 $\max$。对于前者，为一段区间求 $\max$，且左右端点单调不减，维护 $p_{1,j}$ 的单调队列即可。注意边界问题。

时间复杂度 $O(n)$。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace IO{//by cyffff
	
}
const int N=1e7+10;
int n,k,a[N],bel[N],cnt,pos[N],ans,pm[N],sm[N],p0[N],p1[N];
struct node{
	int v,p;
}stk[N];
int hd=1,tl;
int main(){
	n=read(),k=read();
	for(int i=1,las=0;i<=n;i++){
		a[i]=read();
		bel[i]=las;
		if(a[i]){
			p0[i]=p0[i-1]+a[i];
			p1[i]=p1[i-1]+a[i];
		}else{
			p0[i]=p0[i-1]-1;
			p1[i]=p1[i-1]+1;
			pos[++cnt]=i,las=cnt;
		}
	}
	pm[n+1]=sm[n+1]=-2e9;
	for(int i=n;i>=1;i--)
		pm[i]=max(pm[i+1],p1[i]),
		sm[i]=max(sm[i+1],p0[i]);
	for(int i=0,lp=1;i<=n;i++){
		while(hd<=tl&&stk[hd].p<i) hd++;
		int id=bel[i]+k+1;
		if(id>cnt) ans=max(ans,pm[i+1]-p1[i]);
		else{
			int np=pos[id];
			for(;lp<=np-1;lp++){
				while(hd<=tl&&stk[tl].v<p1[lp]) tl--;
				stk[++tl]={p1[lp],lp};
			}
			ans=max({ans,stk[hd].v-p1[i],sm[np]-p0[i]+2*k});
		}
	}
	write(ans);
	flush();
}

再见 qwq~