概要

数列の連続部分列（区間）で、要素の合計がちょうど \(K\) になるものが何通りあるかを数えます。
累積和と出現回数の管理により、全区間を高速に数え上げます。

考察

連続部分列 \(A_l + A_{l+1} + \cdots + A_r\) の和は、累積和を使うと簡潔に表せます。
累積和 \(S_i = A_1 + \cdots + A_i\)（特に \(S_0=0\)）とすると、

• 区間 \([l, r]\) の和は \(S_r - S_{l-1}\)

したがって「区間和が \(K\)」とは

• \(S_r - S_{l-1} = K\)
• \(\Leftrightarrow S_{l-1} = S_r - K\)

という条件になります。
つまり、右端 \(r\) を固定したときに「過去に \(S_r - K\) という累積和が何回出現したか」を数えれば、その分だけ条件を満たす \(l\) が存在します。

素朴な方法がダメな理由

全ての \((l, r)\) を試すと区間は \(O(N^2)\) 個あり、\(N \le 2 \times 10^5\) では間に合いません。
また、\(A_i\) に負の数もあり得るため、しゃくとり法（2ポインタ）で単調性を利用することもできません。

解決策

「累積和の値をキーにして、その出現回数を辞書（ハッシュマップ）で管理」し、各 \(r\) について一瞬で必要数を加算します。

例として \(S_r=10, K=3\) のとき、必要なのは過去の \(S_{l-1}=7\) の個数です。辞書に cnt[7] が入っていれば、その値を答えに足します。

アルゴリズム

1. 累積和 \(prefix\) を \(0\) で開始する（これは \(S_0\)）。
2. 辞書 cnt に「累積和 \(0\) が1回出た」として cnt[0]=1 を入れる。
   （\(l=1\) の区間を数えるために必須）
3. 配列を左から順に見ていき、各要素 \(a\) について:
   • \(prefix \leftarrow prefix + a\)（累積和を更新、つまり \(S_r\) を得る）
   • 条件 \(S_{l-1} = S_r - K\) より、cnt[prefix - K] を答えに加算する
     （存在しない場合は 0）
   • 現在の累積和 \(prefix\) の出現回数を cnt[prefix]++ する
4. 最終的な加算結果を出力する。

この手順で、各 \(r\) について「条件を満たす \(l\) の個数」を重複なく数えられます。

計算量

• 時間計算量: \(O(N)\)（各要素につき辞書操作を定数回）
• 空間計算量: \(O(N)\)（異なる累積和を辞書に保存）

実装のポイント

• cnt[0]=1 を最初に入れるのが重要です。これにより、区間 \([1, r]\) のように左端が1のケースも正しく数えられます。

• 値の範囲が大きく（\(A_i\) は最大 \(10^9\)、累積和はさらに大きくなり得る）、配列ではなく辞書（dict）で回数を管理します。

• ans は最大で \(O(N^2)\) になり得るため、Python の int（多倍長）で問題ありませんが、他言語では 64bit 整数を使う意識が必要です。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, K = data[0], data[1]
    A = data[2:2+N]

    prefix = 0
    cnt = {0: 1}
    ans = 0

    for a in A:
        prefix += a
        ans += cnt.get(prefix - K, 0)
        cnt[prefix] = cnt.get(prefix, 0) + 1

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。