题解 P8945【Inferno】
cyffff
·
·
题解
\text{Link}
第一次 \text{AK div.2}，水个题解不过分吧（
题意
给一个仅包含 -1,0,1 的序列 a。在为 0 的位置中选 k 个更改为 1，其余更改为 -1，使得最大子段和最大，求最大子段和的最大值。
## 思路
看数据范围像几个前缀和就做完了。
枚举左端点减一，设为 $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)$。
代码：
```cpp
#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~