B. Eugene and an array（一个数组中，求和为0的子数组的数量）

https://codeforces.ml/group/DOZ49JViPG/contest/380948/problem/B

题意：定义一个数组为 good array 如果该数组的所有子数组和都不为 0

求一个数组中有多少个子数组是 good array。

思路：运用前缀和查找出和为 0 的子数组，若前缀 pre[i] 之前存在一个相同的 pre[j] (j < i)， 则子数组 [j, i] 的和为 0, 若 pre[i] == 0， 则其本身也是一个和为 0 的子数组。

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
 
const ll N = 2e5 + 5;
 
ll n, pre[N];
map<ll, ll> mp;//记录前缀和相同的最右边的位置
 
void solve()
{
	cin >> n;
	ll ans =n * (n + 1) / 2;//答案最大值为 n * (n + 1) / 2, 后续处理删除不符合条件的子数组
	ll l = 0;//用l标记左边已经处理到的位置，l前面的无需处理，否则会造成重复子数组的删除
	for (ll i = 1, x; i <= n; i++)
	{
		cin >> x;
		pre[i] = pre[i - 1] + x;//预处理前缀和
	}
	for (ll i = 1; i <= n; i++)
	{
		if (mp[pre[i]] + 1 > l && (mp[pre[i]] || !pre[i]))//要删除[mp[pre[i]] + 1, i]的子数组，若mp[pre[i]] + 1 > l则当前可删除为删除过的子数组(删除区间[l, mp[pre[i]] + 1 > l]中的部分元素)
		{
			ans -= (mp[pre[i]] - l + 1) * (n - i + 1);//删除不符合条件并且没有删过的子数组
			l = mp[pre[i]] + 1;//将l更新至最右边， 端点在左边不符合条件的子数组均已删除
		}
		mp[pre[i]] = i;
	}
	cout << ans << '\n';
}