cf #632 div2 C - Eugene and an array (투포인터)

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

 

<문제설명>

-1e9~1e9값을 갖는 최대 1e5의 원소 n개의 배열이 주어진다.

 

배열의 subarray 중 그 subarray의 subarray의 원소합이 0이 아니면 good subarray라고 한다.

 

주어진 배열의 good  subarray 개수를 구하라

 

 

<풀이>

[a1, a2, a3, a4]가 good subarray라면 [a1,a2,a3]도 good subarray이다. 하지만 [a3,a4]가 good subarray일수도 있고 아닐수도 있다.

 

ps[1] = ps[4]인 경우 a[2]~a[4]는 bad subarray이다.

 

문제의 성질을 잘 생각해보면 투포인터로 풀 수 있다.

 

<코드>

ll n, a[MAX], ps[MAX];

int main() {
	FAST; cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		ps[i] = ps[i - 1] + a[i];
	}

	set<ll> s;
	ll lo = 0, hi=0, ans=0;
	s.insert(0);
	while (lo < n) {
		while (hi < n && !s.count(ps[hi + 1])) {
			hi++;
			s.insert(ps[hi]);
		}
		ans += hi - lo;
		s.erase(ps[lo]);
		++lo;
	}
	cout << ans << '\n';
}