← 返回题目列表

AtCoder · awc0004_e

E. 间隔总和

中文机器翻译题面 查看原题

分数: 433 分

问题陈述

高桥有一系列 N 整数 A = (A_1, A_2, \ldots, A_N)。每个元素 A_i 可能取负值。

高桥想要选择一个 连续子数组 来自该序列,使其元素之和恰好等于整数 K,其中 K 是目标总和值。求出选择这样一个子数组的方法的数量。

更准确地说,找到整数对的数量 (l, r) 满意 1 \leq l \leq r \leq N 这样

$$A_l + A_{l+1} + \cdots + A_r = K$$

约束

  • 1 \leq N \leq 2 \times 10^5
  • -10^9 \leq K \leq 10^9
  • -10^9 \leq A_i \leq 10^9
  • 所有输入均为整数

输入

N K
A_1 A_2 \cdots A_N
  • 第一行包含整数 N 表示序列中元素的个数和整数 K 代表目标总和值,以空格分隔。
  • 第二行包含整数 A_1, A_2, \ldots, A_N 表示序列的每个元素,以空格分隔。

输出

打印整数对的数量 (l, r) 满足条件,在一行上。


示例输入 1

5 5
1 2 3 4 5

示例输出 1

2

示例输入 2

6 3
1 -1 2 3 -2 4

示例输出 2

3

示例输入 3

10 0
1 -1 0 0 2 -2 0 3 -3 0

示例输出 3

28