CF - 1333C

题目定义good数列：不含有和为0子串的的数列。

给定一个数组，问其中多少子串是good数列。

运用dp的思想，设dp[i]是前i个数的good子串数量，已知dp[i-1]求dp[i]时，就要找到从1到i，起点pos最靠右的子串，该子串和为0，那么新增的good子串数就是i-pos。

为了维护pos，前缀和sum[i]已知，只要找到sum[k]，sum[k]==sum[i]，就知道了包含i元素的起点最靠右的0子串(k+1)，至于不包含i元素的0子串，那就一定在求dp[i]之前已经求出来了。用map维护当前前缀和最靠右位置。

• 代码
• //pos是【起点最靠右的0子串】的起点-1，初始化-1；
• //map中要插入p[0] = 0;

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<list>
#include<stack>
#include<queue>
#include<vector>
#define cl (k<<1)
#define cr (k<<1|1)
#define Mid ((a[k].l+a[k].r)>>1)
#define mem(a,x) memset(a,x,sizeof(a))
using namespace std;
#define bug printf("???\n")

typedef long long LL;

const int Inf=0x3f3f3f3f;
const double eps=1e-8;
const int maxn=2e5+50;

map<LL,int>p;
LL sum[maxn];


int main()
{
    int n;
    cin>>n;
    LL ans=0;
    p[0] = 0;
    int pos=-1;
    for(int i=1; i<=n; i++){
        scanf("%lld",&sum[i]);
        sum[i] += sum[i-1];
        if(p.count(sum[i])) pos = max(pos, p[sum[i]]);
        ans += i-(pos+1);
        p[sum[i]] = i;
    }
    cout<<ans<<endl;
}