[R40B]Yet another sequence problem - 代码源竞赛平台

时空限制

1s/512M

题目描述

给定一个长度为 $n$ 的正整数数组 $a$ 和一个正整数 $k$。

我们定义数组中的下标 $i$ 是“极好的”，当且仅当数组中存在一个连续区间 $[l, r]$（$1 \le l \le r \le n$），使得该区间的数字的和加上 $a_i$ 恰好等于 $k$。

即满足：

$$\sum_{j=l}^{r}a_j + a_i = k$$

其中，符号 $\sum_{j=l}^{r}a_j$ 表示数组 $a$ 中下标从 $l$ 到 $r$ 的所有数字之和，即 $a_l + a_{l+1} + \dots + a_r$。

请你统计数组 $a$ 中有多少个下标 $i$ 是“极好的”。

格式

输入格式

第一行包含两个正整数 $n, k$，分别表示数组长度和目标和。

第二行包含 $n$ 个正整数，第 $i$ 个数表示 $a_i$。

输出格式

输出一个整数，表示“极好的”下标 $i$ 的数量。

样例

样例输入 #1

5 7
5 2 3 4 1

样例输出 #1

4

样例解释 #1

数组为 [5, 2, 3, 4, 1]，目标值 $k=7$。我们需要找到区间和为 $k - a_i$ 的区间。

• 对于第 $1$ 个数 $5$ ($i=1$)：需要区间和为 $7-5=2$。选择区间 $[2, 2]$（元素为 $2$），满足条件。
• 对于第 $2$ 个数 $2$ ($i=2$)：需要区间和为 $7-2=5$。选择区间 $[1, 1]$（元素为 $5$），满足条件。
• 对于第 $3$ 个数 $3$ ($i=3$)：需要区间和为 $7-3=4$。选择区间 $[4, 4]$（元素为 $4$），满足条件。
• 对于第 $4$ 个数 $4$ ($i=4$)：需要区间和为 $7-4=3$。选择区间 $[3, 3]$（元素为 $3$），满足条件。
• 对于第 $5$ 个数 $1$ ($i=5$)：需要区间和为 $7-1=6$。无法在数组中找到和为 $6$ 的区间。

因此，共有 $4$ 个极好的下标。

数据规模

对于 $100\%$ 的数据，满足 $1 \le n \le 5000$，$1 \le a_i, k \le 5000$。