N-sum Ranges

この問題の解法はほとんどAGC 023 Zero-Sum Rangesと同様です

N-Sum Ranges
$S$ を長さ $N + 1$ の数列とし、$S_0 = 0, S_i = S_{i−1} + A_i$ とします。
ある連続する部分列の総和は、 $S$ の 2 要素の差です。
よって、和が $K$ になる連続する部分列の数は、$S$ の2点$i,j(i<j)$を選び,$S_j-S_i=K$となる $i,j$を選ぶ方法の数に等しいです。
これは、$S$ の要素に それぞれの数字が何回出てきたかをmap などでカウントしておき、$S$の要素$i$に対してmap内にある$S_i-K$の数の和が答えとなります。
よってこの問題は $O(N)$で解けました