【菜笔cf刷题日常-1600】C. Good Subarrays（思维，前缀和）

链接：Problem - 1398C - Codeforces

思路：

考虑每一个新加入的数对于原有序列（长度、数的总和）需求的变化：

如 1 的加入对于原有序列需求无变化；2 的加入需要原有序列长度增加 1 ；0 的加入需要原有序列数的总和增加 1 ；……

因此，将每个数减 1（如 1 变为 0 ， 0 变为 -1 ）来代表这个数的新加入对于原有序列的变化。

然后计算前缀和。如果其中有两个前缀和相同，说明在这两个中间的区间总和为 0，即存在符合要求的好子数组。

方法为使用map记录所有前缀和的出现次数，利用公式计算好子数组数量。注意当前缀和为 0 的时候还需要加上其本身的数量。

code：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,t,k,l,r,q,p,x,idx,res,cnt,sum,flag,maxx,minn;
const int N=200010;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f3f3f3f3f;
int a[N],b[N];

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);

	cin>>t;
	while(t--){
		map<int,int> mp;
		vector<int> b;
		cin>>n;
		int tem=0;
		for(int i=1;i<=n;i++){
			char o;
			cin>>o;
			a[i]=o-'0'-1;
			tem+=a[i];
			if(mp[tem]==0){
				b.push_back(tem);
			}
			mp[tem]++;
		}
		sum=0;
		for(int i=0;i<b.size();i++){
			tem=mp[b[i]];
			if(b[i]==0){
				sum+=(tem+1)*tem/2;
			}
			else if(tem>=2){
				sum+=(tem-1)*tem/2;	
			}
		}
		cout<<sum<<'\n';
	}
	return 0;
}