F. Yamakasi

时间限制

• 每个测试的时间限制：3秒
• 每个测试的内存限制：256MB

题目描述

给定一个整数数组 $a_1, a_2, \dots, a_n$，以及两个整数 $s$ 和 $x$。
请统计数组中**所有子段（连续子数组）**的数量，满足以下两个条件：

1. 子段元素和等于 $s$。
2. 子段中的最大值等于 $x$。

更正式地，统计满足 $1 \leq l \leq r \leq n$ 的对 $(l, r)$，使得：

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

输入格式

• 第一行输入一个整数 $t$，表示测试用例的数量。$(1 \leq t \leq 10^4)$
• 每个测试用例的第一行输入三个整数 $n, s, x$：
  • $1 \leq n \leq 2 \times 10^5$
  • $-2 \times 10^{14} \leq s \leq 2 \times 10^{14}$
  • $-10^9 \leq x \leq 10^9$
• 第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示数组 $a$：
  • $-10^9 \leq a_i \leq 10^9$

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

输出格式

每个测试用例输出一行，表示满足条件的子段数量。

示例输入

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$