← 返回题目列表

Codeforces · 1994/C

C. 饥饿游戏

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

Yaroslav 正在玩一款电脑游戏,在其中一个关卡中,他遇到了排列成一排的 $$$n$$$ 蘑菇。每种蘑菇都有自己的毒性水平;从一开始第 $$$i$$$ 蘑菇的毒性级别为 $$$a_i$$$。雅罗斯拉夫可以选择两个整数 $$$1 \le l \le r \le n$$$,然后他的角色会从左到右轮流一一吃掉这个分段中的蘑菇,即数字为 $$$l、l+1、l+2、\ldots、r$$$ 的蘑菇。

该角色的毒性等级为$$$g$$$,最初等于$$$0$$$。电脑游戏由数字 $$$x$$$ 定义——任何给定时间的最大毒性水平。当食用毒性级别为 $$$k$$$ 的蘑菇时,会发生以下情况:

1.角色的毒性等级增加$$$k$$$。
2. 如果 $$$g \leq x$$$,则过程继续;否则,$$$g$$$ 变为零并且该过程继续。

Yaroslav 开始感兴趣的是有多少种方法可以选择 $$$l$$$ 和 $$$r$$$ 的值,使得 $$$g$$$ 的最终值不为零。帮助雅罗斯拉夫找到这个号码!

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — 测试用例的数量。然后是测试用例的描述。

每个测试用例的第一行包含两个整数 $$$n$$$, $$$x$$$ ($$$1 \leq n \leq 2 \cdot 10^5, 1 \le x \le 10^9$$$) – 蘑菇的数量和最大毒性水平。

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

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

输出

对于每个测试用例,输出一个数字 - 子段的数量,使得 $$$g$$$ 的最终值不会为零。

示例

输入 #1

5
4 2
1 1 1 1
3 2
1 2 3
1 6
10
6 3
1 2 1 4 3 8
5 999999999
999999999 999999998 1000000000 1000000000 500000000

输出 #1

8
2
0
10
7

注意

在第一个测试用例中,子段 $$$(1, 1)$$$、$$$(1, 2)$$$、$$$(1, 4)$$$、$$$(2, 2)$$$、$$$(2, 3)$$$、$$$(3, 3)$$$、$$$(3, 4)$$$ 和$$$(4, 4)$$$ 合适。

在第二个测试用例中,非零 $$$g$$$ 将仅保留在子段 $$$(1, 1)$$$ 和 $$$(2, 2)$$$ 上。

在第三个测试用例中,在唯一可能的子段上,$$$g$$$ 将为零。