← 返回题目列表

Codeforces · 2006/D

D. 虹膜及相关产品

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

Iris 刚刚在数学课上学会了乘法。然而,由于她的大脑无法承受太复杂的计算,她无法将两个乘积大于$$$k$$$的整数相乘。不然她的脑子可能会爆炸!

她的老师每天都会给她布置一项艰巨的任务,作为她每天的暑假作业。现在给她一个由 $$$n$$$ 元素组成的数组 $$$a$$$,她需要计算每两个相邻元素的乘积(即 $$$a_1 \cdot a_2$$$、$$$a_2 \cdot a_3$$$ 等)。 Iris 希望她的大脑安全地工作,为了做到这一点,她希望修改数组 $$$a$$$,使得 $$$a_i \cdot a_{i + 1} \leq k$$$ 对于每个 $$$1 \leq i < n$$$ 成立。她可以执行两种类型的操作:

1. 她可以以任意方式重新排列数组 $$$a$$$ 的元素。
2. 她可以选择数组 $$$a$$$ 中的任意元素,并将其值更改为 $$$1$$$ 到 $$$k$$$ 之间的任意整数。

Iris 希望最大限度地减少她使用的 $$$2$$$ 类型的操作数量。

然而,这完全不是暑假的结束!暑假持续 $$$q$$$ 天,在第 $$$i$$$ 天,Iris 被要求解决子数组 $$$b_{l_i}, b_{l_i + 1}, \ldots, b_{r_i}$$$ 的数学作业。帮助 Iris 并告诉她每天需要执行的最少 $$$2$$$ 类型操作。请注意,每天的操作都是独立的,即数组 $$$b$$$ 不会更改。

输入

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

每个测试用例的第一行包含三个整数 $$$n$$$、$$$q$$$ 和 $$$k$$$ ($$$2 \leq n \leq 10^5$$$, $$$1 \leq q \leq 10^5$$$, $$$1 \leq k \leq 10^6$$$) — 数组的长度$$$b$$$、天数以及乘法计算的上限。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_i \leq k$$$) — 数组 $$$b$$$ 的元素。

接下来是 $$$q$$$ 行,其中第 $$$i$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \leq l_i < r_i \leq n$$$) — 第 $$$i$$$ 天的子数组的边界。

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

输出

对于每个测试,输出一行包含 $$$q$$$ 整数 — 每天所需的 $$$2$$$ 类型的最小操作数。

示例

输入 #1

5
3 1 1
1 1 1
1 3
3 2 10
1 10 9
1 3
2 3
5 4 2
2 2 2 2 2
1 2
2 4
2 5
1 5
6 5 10
3 2 5 10 10 1
1 4
3 6
1 6
2 5
5 6
10 10 10
10 9 8 7 6 5 4 3 2 1
1 10
1 9
1 8
1 7
2 10
3 10
4 10
5 10
3 9
6 8

输出 #1

0 
0 1 
1 1 2 2 
1 1 1 1 0 
3 3 4 3 2 2 1 1 2 1

注意

在第一个测试用例中,由于 Iris 总是可以将 $$$1$$$ 和 $$$1$$$ 相乘,因此不需要任何操作,所以答案是 $$$0$$$。

在第二个测试用例中,第一天的作业是$$$[1, 10, 9]$$$。 Iris 可以重新排列其元素以获得 $$$[9, 1, 10]$$$,因此不需要 $$$2$$$ 类型的操作。第二天的作业是$$$[10, 9]$$$,她可以改变一个元素得到数组$$$[1, 9]$$$,所以需要一次$$$2$$$类型的操作。