CF 1333C Eugene and an array

One . The question

Give you an array , I want you to find several good sub segments in the array （ Good sub segment ： The does not contain any sub segments so that the sum of these sub segments is 0）

Two . Use Algorithm

The prefix and

3、 ... and . Ideas

Data range 2e5 It seems that it is probably a problem that can be solved by enumerating once

Let's start with the first place , Enumerating to each location, we make the answer += All good sub segments ending in the current position and , According to the idea of prefix and , This sub segment cannot contain both prefixes and equal points . So when enumerating the last position of the sub segment , Maintain the frontmost boundary that a sub segment can extend to each time .

So how to maintain this front boundary （ It is not advisable to ） Well ？ The prefix and

During our enumeration , If the current prefix and = The prefixes and conditions enumerated above , Then the section between sum=0, Therefore, maintain the front boundary of the selected sub segment as the first prefix of the same prefix and the next position of the location .

Why is this position? For example

Array 2 -1 1 2 3

When i=3  here i=1 and i=3 The prefix and are equal At this time, sub segment -1 1 sum=0 Give Way pos=2, This position is nogood The beginning of the sub segment , The prefix and sum[i]- The prefix and sum[j] He is actually i+1 To j paragraph , So the i+1 If you can't take it, it won't appear behind sum=0 The situation of the .

For example i=3 The prefix and =6

stay i=7 The prefix and =6  that The top position is updated to pos=4.

So at this time good The sub segment can be （ Marked by position ）567/67/7 That is to say i-pos Three sub segments （ Location pos Is a sub segment and can be 0 The boundary of is not desirable ）

A knowledge ：map  In the past, you can also find out whether it has existed ！！（.count(x)）

Four . Code

#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;
    
}