BOJ 25332 - 수들의 합 8

April 11, 2023

$A_i \coloneqq A_i-B_i$ 라 하자.

결국 어떤 구간의 합이 $0$ 이 되는 것을 찾는 것이므로 $\sum_{i=0}^k A_i -\sum_{i=0}^u A_i$ 중 $0$이 되는 것의 개수를 찾아주면 된다.

void solve() {
   int n;
   cin >> n;
   vi a(n), b(n);
   fv(a);
   fv(b);
   for (int i = 0; i < n; i++) a[i] -= b[i];
   map<ll, int> cnt;
   ll sum = 0, ans = 0;
   cnt[0] = 1;
   for (int i = 0; i < n; i++) {
      sum += a[i];
      ans += cnt[sum];
      cnt[sum]++;
   }
   cout << ans;
}