Eugene喜欢使用数组。今天，他需要你的帮助来完成一项具有挑战性的任务。
数组c是数组b的子数组，如果c可以从b中通过从开始删除几个(可能是零或全部)元素和从结束删除几个(可能是零或全部)元素来获得。
如果该数组的每个非空子数组，该子数组的元素的和都是非零，则我们称非空数组为good。例如，数组[−1,2，−3]是好的，因为所有数组[−1]，[−1,2]，[−1,2，−3]，[2]，[2，−3]，[−3]的元素和都是非零的。但是，数组[- 1,2，- 1，- 3]并不好，因为它的子数组[- 1,2，- 1]的元素和为0。
帮助Eugene计算一个给定数组a的非空良子数组的数目。
输入
输入的第一行包含一个整数n(1≤n≤2×105)——数组a的长度。
输入的第二行包含n个整数a1,a2，…，an(−109≤ai≤109)- a的元素。
输出
输出一个整数——a的好子数组的数目。
例子
inputCopy
3.
1 2 3
outputCopy
5
inputCopy
3.
41 -41 41
outputCopy
3.
请注意
在第一个样本中，下列子阵列是良好的:[1]，[1,2]，[2]，[2，−3]，[−3]。然而，子数组[1,2，−3]并不好，因为它的子数组[1,2，−3]的元素和等于0。
在第二个示例中，大小为1的三个子数组是惟一的好子数组。与此同时，子数组[41，−41,41]并不好，因为它的子数组[41，−41]的元素和等于0。
题解：
从左往右遍历，用一个map存储当前前缀和的值是否在之前出现过。如果出现过，那么之前的位置到当前的位置的这段序列是不合法的，根据这个方法可以统计出正确答案，时间复杂度是O(N)
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=2e5+100; int a[maxn]; map<ll,ll> pos; int main () { int N; scanf("%d",&N); pos[0]=1; ll sum=0,ans=0,Max=1; for (int i=2;i<=N+1;i++) { scanf("%d",&a[i]); sum+=a[i]; if (pos[sum]!=0) Max=max(Max,pos[sum]+1); ans+=i-Max; pos[sum]=i; } printf("%lld ",ans); }