[CF 1333C] Eugene and an array

[CF 1333C] Eugene and an array - 1700

 

문제 설명 : 

배열 a의 subarray 중에서,  모든 원소의 합이 0이 아닌 경우의 개수를 구하여라.

 

풀이 : 

subarray의 합이 0이 된다는 말은 바꿔 얘기하면, prefix sum배열을 만들었을 때 값이 같은 원소가 두개 이상 존재한다는 뜻이다(그 두 지점을 각각 a,b라고 했을 때 pref[b] - pref[a-1] == 0이 될 것이므로). 따라서 왼쪽->오른쪽으로 pref배열을 돌면서 나오는 값을 map에다 집어 넣는다. key값은 누적합 값 자체를 넣을 것이고 value에는 그 값이 가장 최근에 몇 번째 인덱스에 등장했느냐를 저장한다(정확히는 등장한 인덱스 +1의 위치). 그러면 현재 prefix sum과 일치한 값이 나왔던 인덱스 전까지의 subarray는 절대로 0이 아니었다고 확실할 수 있고, 그 사이에 있었던 원소의 개수만큼 더해주면 된다.

 

주의할 점 : 

 

배운 점 : 

 

코드 :

int main(){
    int n;  scanf("%d",&n);

    ll sum=0,ans=0;
    int last=0;
    map<ll,int> pos;
    pos[0]=1;

    for(int i=1 ; i<=n ; i++){
        ll x;   scanf("%lld",&x);
        sum += x;
        last = max(last, pos[sum]);
        pos[sum] = i+1;
        ans += i-last;
    }
    printf("%lld\n",ans);
    

    return 0;
}