AtCoder Beginner Contest 233 D - Count Interval【Python】
https://atcoder.jp/contests/abc233/tasks/abc233_d
コンテスト中は累積和のみ実装しその後の高速化の方法がわからず解けませんでした。
以下は公式の解説動画
https://www.youtube.com/watch?v=-6clqT8n794
そのままの実装です。
from collections import defaultdict N, K = map(int, input().split()) A = list(map(int, input().split())) S = [0] for i in range(N): S.append(A[i] + S[i]) ans = 0 d = defaultdict(int) for i in range(N + 1): ans += d[S[i]] d[S[i] + K] += 1 print(ans)