CF 1333C Eugene and an array

一.题意

给你一个数组，要你找出数组中有几个好子段（好子段：该不包含任何一个子段使得此子段之和为0）

二.用到算法

前缀和

三.思路

数据范围2e5看来大概是枚举一遍就可以解决的问题

我们从第一个位置开始枚举，枚举到每个位置我们使得答案+=以当前位置结尾的全部好子段和，根据前缀和的思想，此子段中不能同时包含前缀和相等的两个点。因此我们在枚举子段最后位置的时候，每次维护一个子段可以延申到的最前面的边界。

那么如何维护这个最前边界（不可取到）呢？就用到了前缀和

我们枚举过程中，如果出现了当前前缀和=前面枚举过的前缀和的情况，那这之间的一段sum=0，因此维护选取的子段的最前面边界为相同前缀和的第一个前缀和所在位置的下一个位置。

为什么是这个位置呢打个比方

数组2 -1 1 2 3

当i=3  此时 i=1 和 i=3前缀和相等了 这时候子段-1 1 sum=0 让pos=2，这个位置是nogood子段的开头位置，前缀和sum[i]-前缀和sum[j]他其实是i+1到j段 ，所以把i+1不能取那后面就不会出现sum=0的情况了。

比如在i=3 前缀和=6

在i=7 前缀和=6  那么 最前位置更新到pos=4。

那么此时 good子段可以为（以位置为标志）567/67/7 也就是i-pos三个子段（位置pos为子段和可以为0的边界不可取）

一个知识 ：map  原来也可以查找是否存在过！！（.count(x)）

四.代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>

using namespace std;

const int N = 2e5+10;
typedef long long LL;
LL sum;
map<LL,LL> cnt;
int main()
{
    int n;
    cin>>n;
    LL pos=0;
    cnt[0]=0;
    LL ans=0;
    for(int i=1;i<=n;i++)
    {
        int a;
        cin>>a;
        sum+=a;
       
        if(cnt.count(sum))
        {
            pos=max(pos,cnt[sum]+1);
        }
        ans+=i-pos;
        cnt[sum]=i;
    }
    cout<<ans<<endl;
    
}