区间计数

题目描述

给定长度为 $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$

输出格式

输出答案。

样例

6 5
8 -3 5 7 0 -4

3

$(l,r)=(1,2),(3,3),(2,6)$ 是满足条件的三个整数对。

2 -1000000000000000
1000000000 -1000000000

0

也可能不存在满足条件的整数对。

数据范围

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