Count Interval

题目描述

给定一个长度为 $N$ 的数列 $A=(A_1,A_2,\ldots,A_N)$，以及一个整数 $K$。

请问 $A$ 的所有连续子序列中，元素之和等于 $K$ 的有多少个？ 也就是说，有多少整数对 $(l, r)$ 满足以下所有条件：

• $1 \leq l \leq r \leq N$
• $\displaystyle\sum_{i=l}^{r}A_i = K$

输入格式

输入以如下格式从标准输入中给出。

$N$ $K$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

6 5
8 -3 5 7 0 -4

输出 #1

3

输入输出样例 #2

输入 #2

2 -1000000000000000
1000000000 -1000000000

输出 #2

0

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $|A_i| \leq 10^9$
• $|K| \leq 10^{15}$
• 输入中的所有值均为整数。

样例解释 1

满足条件的 $3$ 组 $(l, r)$ 分别为 $(1,2)$、$(3,3)$、$(2,6)$。

样例解释 2

也有可能不存在满足条件的 $(l, r)$ 组。