← 返回题目列表

Codeforces · 2121/F

F. 山卡西

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

给定一个整数数组 $$$a_1、a_2、\ldots、a_n$$$ 和两个整数 $$$s$$$ 和 $$$x$$$。计算数组中元素总和等于 $$$s$$$ 且最大值等于 $$$x$$$ 的子段数。

更正式地,计算对 $$$1 \leq l \leq r \leq n$$$ 的数量,使得:

  • $$$a_l + a_{l + 1} + \ldots + a_r = s$$$。
  • $$$\max(a_l, a_{l + 1}, \ldots, a_r) = x$$$。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$s$$$ 和 $$$x$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$-2 \cdot 10^{14} \leq s \leq 2 \cdot 10^{14}$$$, $$$-10^9 \leq x \leq 10^9$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出元素总和等于 $$$s$$$ 且最大值等于 $$$x$$$ 的数组子段数。

示例

输入
复制

9
1 0 0
0
1 -2 -1
-2
3 -1 -1
-1 1 -1
6 -3 -2
-1 -1 -1 -2 -1 -1
8 3 2
2 2 -1 -2 3 -1 2 2
9 6 3
1 2 3 1 2 3 1 2 3
13 7 3
0 -1 3 3 3 -2 1 2 2 3 -1 0 3
2 -2 -1
-2 -1
2 -2 -1
-1 -2

输出
复制

1
0
2
0
2
7
8
0
0

注意

在第一个测试用例中,合适的子段是 $$$l = 1$$$, $$$r = 1$$$。

在第三个测试用例中,合适的子段是 $$$l = 1$$$、$$$r = 1$$$ 和 $$$l = 3$$$、$$$r = 3$$$。

在第五个测试用例中,合适的子段是 $$$l = 1$$$、$$$r = 3$$$ 和 $$$l = 6$$$、$$$r = 8$$$。

在第六个测试用例中,合适的子段是 $$$r = l + 2$$$ 的子段。

在第七个测试用例中,以下子段是合适的:

  • $$$l = 1$$$,$$$r = 7$$$。
  • $$$l = 2$$$,$$$r = 7$$$。
  • $$$l = 3$$$,$$$r = 6$$$。
  • $$$l = 4$$$,$$$r = 8$$$。
  • $$$l = 7$$$,$$$r = 11$$$。
  • $$$l = 7$$$,$$$r = 12$$$。
  • $$$l = 8$$$,$$$r = 10$$$。
  • $$$l = 9$$$,$$$r = 13$$$。