102333: [AtCoder]ABC233 D - Count Interval

Problem Statement

Given is a sequence of length $N$: $A=(A_1,A_2,\ldots,A_N)$, and an integer $K$.

How many of the contiguous subsequences of $A$ have the sum of $K$?
In other words, how many pairs of integers $(l,r)$ satisfy all of the conditions below?

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

Constraints

• $1\leq N \leq 2\times 10^5$
• $|A_i| \leq 10^9$
• $|K| \leq 10^{15}$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

6 5
8 -3 5 7 0 -4

Sample Output 1

3

$(l,r)=(1,2),(3,3),(2,6)$ are the three pairs that satisfy the conditions.

Sample Input 2

2 -1000000000000000
1000000000 -1000000000

Sample Output 2

0

There may be no pair that satisfies the conditions.

问题描述

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

限制条件

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

输入

输入将从标准输入以以下格式给出：

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

输出

输出答案。

样例输入 1

6 5
8 -3 5 7 0 -4

样例输出 1

3

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

样例输入 2

2 -1000000000000000
1000000000 -1000000000

样例输出 2

0

可能没有满足条件的整数对。