Zero-Sum Ranges [AtCoder Grand Contest 023 A]

https://agc023.contest.atcoder.jp/tasks/agc023_a

解法

https://agc023.contest.atcoder.jp/submissions/2433904

よくある方針「右側を固定して効率よく処理する」を使う。
右端を固定して考えて、連続する部分列の総和が0となる左端は何通りあるかを高速に数えたい。
これは累積和を使って答えていこう。

区間[l,r]の総和が0であるlの組合せ
↓
区間[0,l-1]の総和と区間[0,r]の総和が等しいlの組合せ
　
このように言い換えて考える。
これは「cnt[x] := 区間の総和がxである[0,l]のlの組合せ」を用意することで解決できる。
頭から累積和を取っていき、cntを更新しながら答えを数え上げよう。

int N, A[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
 
    ll ans = 0;
    map<ll, int> cnt;
    cnt[0] = 1;
    ll sm = 0;
    rep(i, 0, N) {
        sm += A[i];
        ans += cnt[sm];
        cnt[sm]++;
    }
    cout << ans << endl;
}