给定一个长度为 \(n\) 的由 \(0,1\) 组成的整数序列 \(A=(A_1,A_2,\cdots,A_n)\) 。你可以做以下的操作一次且仅一次：
- 选择 \(A\) 的一个连续的子段，对该子段进行反转操作，也就是将 \(0\) 变成 \(1\) ,将 \(1\) 变成 \(0\) 。注意，你可以选择一个空字段，这就相当于你什么都没有做。
最后 \(A\) 中的 \(1\) 的个数，是你能获得的分数。请问你有多少种可能的得分。
样例 #1
样例输入 #1
4
0 1 1 0
样例输出 #1
4
样例 #2
样例输入 #2
5
0 0 0 0 0
样例输出 #2
6
样例 #3
样例输入 #3
6
0 1 0 1 0 1
样例输出 #3
3
提示
- $ 1\ \leq\ N\ \leq\ 3\ \times\ 10^5 $
- $ 0\ \leq\ A_i\ \leq\ 1 $
analysis:
首先，设 ans为操作后数组中 1 的个数。那么就有一个结论：ans 的取值范围肯定是一段连续的正整数。
因为假设你取了一段区间 [l,r]，无论你下次取 [l−1,r]、[l+1,r]、[l,r−1] 还是 [l,r+1]，都会对 ans 产生 1 的影响。
所以我们可以想到，求 ans 取到的最大值 ansmx 和最小值 ansmn，那么 ans的取值的数量就为 [ansmn,ansmx]的元素个数。
如何求这个值？
考虑到每次多取一个数就会对 ans 产生 1 的影响，所以可以定义数组 s，si 为取 ai 对答案造成的影响，那么 si 是由 1 或 −1−1 组成的。
那么就可以找区间和最大的 s 区间，与区间和最小的 ss 区间。
所以可以想到前缀和。
用前缀和维护区间和最大值和最小值不多赘述。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n, a[300005], b[300005], maxn, minn, ansmax, ansmin;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]), b[i] = b[i - 1] + (a[i] == 0 ? 1 : -1);
for (int i = 1; i <= n; i++) {
ansmax = max(ansmax, b[i] - minn);
//b[i]-minn 就是以当前节点为结尾所能产生的最大值
ansmin = min(ansmin, b[i] - maxn);
//b[i]-maxn 就是以当前节点为结尾所能产生的最小值
maxn = max(maxn, b[i]);
minn = min(minn, b[i]);
}
printf("%d", ansmax - ansmin + 1);
return 0;
}