C. Eugene and an array

https://codeforces.com/contest/1333/problem/C

binary search 이분 탐색 data structures  자료구조 hashing 해 implementation 실행   two pointers 투 포인터

C. Eugene and an array

Eugene likes working with arrays. And today he needs your help in solving one challenging task.

An array c is a subarray of an array b if c can be obtained from b by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Let's call a nonempty array good if for every nonempty subarray of this array, sum of the elements of this subarray is nonzero. For example, array [−1,2,−3] is good, as all arrays [−1], [−1,2], [−1,2,−3], [2], [2,−3], [−3] have nonzero sums of elements. However, array [−1,2,−1,−3] isn't good, as his subarray [−1,2,−1] has sum of elements equal to 0.

Help Eugene to calculate the number of nonempty good subarrays of a given array a.

Input

The first line of the input contains a single integer n (1≤n≤2×10)  — the length of array a.

The second line of the input contains n integers  — the elements of a.

Output

Output a single integer  — the number of good subarrays of a.

Examples

3

1 2 -3

5

3

41 -41 41

3

Note

In the first sample, the following subarrays are good: [1], [1,2], [2], [2,−3], [−3]. However, the subarray [1,2,−3] isn't good, as its subarray [1,2,−3] has sum of elements equal to 0.

In the second sample, three subarrays of size 1 are the only good subarrays. At the same time, the subarray [41,−41,41] isn't good, as its subarray [41,−41] has sum of elements equal to 0.

누적합[a]와 누적합[b]가 같다면(즉, map에 이미 있다면), a+1 ~ b의 '원소'들의 합이 0이다. 

여기서는 a = j, b = i 라고 하자.

29, 37번 째 줄에서 max가 들어가는 이유는 더 최신 상태의 j를 갱신하기 위해서다.(각 예시는 max가 없을 때의 반례)

예를 들어, 37번 째 줄 같은 경우 max(j, m[sum] + 1)이 아닌 j = m[sum] + 1일 때,

누적합을 나열해보자면(예시)

-4 (m[-4] = 1)

-2 (m[-2] = 2)

 0 (j가 3으로 갱신) 

-2 (j가 m[-2] + 1로 갱신 = 3) 

-4 (j가 m[-4] + 1로 갱신 = 2) → 여기서 잘못됨.

j는 특정 구간을 유지해주는 인덱스이므로(즉, 이미 같은 값이 있을 때 활용된다),

같은 값이 있을 때는 j를 더 큰 값(오른쪽)으로 갱신해야 한다.

이렇게 해야 i - j에서 잘못된(합이 0인 구간) 구간도 셈하는 것을 막을 수 있다.

#include<bits/stdc++.h>
 
using namespace std;
 
#define LL long long
 
int n;
map<LL, int> m;
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\buba.in.6", "r", stdin);
    cin.tie(0);
 
    scanf("%d", &n);
    
    LL input, sum = 0, cnt = 0;
    int j = 0;
    m[0] = 0;
 
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &input);
        sum += input;
 
        // 이미 있다면
        if (m.count(sum)) {
            // 만약 0이라면
            if (sum == 0 && m[0] == 0) {
                j = max(j, 1);
                /*
                max가 없을 때의 반례
                4
                2 -1 1 0
                */
            }
            else {                
                j = max(j, m[sum] + 1);
                /*
                max가 없을 때의 반례
                5
                -4 2 2 -2 -2
                */
            }
        }
 
        cnt += i - j; // 합이 0이 아닌 구간의 개수만 셈한다.
        m[sum] = i;        
    }
 
    printf("%lld\n", cnt);
 
    return 0;
}