CF2121F.Yamakasi

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给你一个长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$ 和两个整数 $s$ 和 $x$ 。请你计算元素之和等于 $s$ 并且最大值等于 $x$ 的子数组的数量。
更具体地说，计算有多少对 $1 \le l \le r \le n$ 满足以下条件：

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

输入格式

本题目含有多测。
第一行包含一个整数 $t(1 \le t \le 10^4)$ ，表示测试用例的个数。
每个测试用例的第一行包含三个整数 $n$ ， $s$ 和 $x(1 \le n \le 2 \times 10^5,-2 \times 10^{14} \le s \le 2 \times 10^{14},-10^9 \le x \le 10^9)$ 。
每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n(-10^9 \le a_i \le 10^9)$ 。
保证 $\sum n \le 2 \times 10^5$ 。

输出格式

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

输入输出样例

输入#1

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

说明/提示

在第一个测试用例中，满足条件的子数组是 $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$

输入解题思路，AI测评打分。不知道怎么写?

首页