自动搬运

查看原文

来自洛谷，原作者为

	weifengzhaomi 加油，不要辜负对朱前泰说的话

搬运于2025-08-24 21:17:25，当前版本为作者最后更新于2025-07-03 08:56:42，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

哎呀，看各位大佬写的什么树状数组，本蒟蒻瑟瑟发抖啊。

其实，各位大佬想复杂了，这道题其实就是一个简单的前缀和！

思路：

首先，我们思考一下 $20$ 分的部分分该怎么写。

我们先用一个前缀和数组预处理一下原来的数组，然后，我们暴力枚举两个点，用前缀和快速求出这个区间的 $0$ 和 $1$ 的个数。

时间复杂度：$O(n ^ 2)$。

预期得分 $20$ 分。

然后，我们借助 $20$ 分的思想来思考满分做法该怎么做。

我们用一个变量 $cnt$ 记录到当前满足条件的区间的个数，再加到答案里。

那么，我们依次分类讨论。

1. 当前字符为 $1$：

   所有以前一个字符结尾的满足条件的区间再加上一个 $1$ 后一定还满足条件，而 $0$ 和 $1$ 相等的区间也会变得满足条件，对应计算即可。

2. 当前字符为 $0$：

   所有以前一个字符结尾的不满足条件的区间加上一个 $0$ 后一定还是不满足条件，$0$ 和 $1$ 相等的区间也会变得不满足条件，同样对应计算。

注意：最后的答案会爆int。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
char s[10000010];
int n,ans,cnt,res,f[20000010];
signed main(){
	scanf("%lld%s",&n,s + 1),f[n] = 1;
	for (int i = 1;i <= n;i++){
		if (s[i] == '1') cnt += f[n + res],res++;
		else cnt -= f[n + res - 1],res--;
		f[n + res]++,ans += cnt;
	}
	printf("%lld\n",ans);
}