CF2006D Iris and Adjacent Products

Iris 刚刚在数学课上学会了乘法。然而，由于她的大脑无法承受过于复杂的计算，她不能将两个乘积大于 $k$ 的整数相乘，否则她的大脑可能会爆炸！ 她的老师每天都会布置一道难题作为暑假作业。现在给定一个包含 $n$ 个元素的数组 $a$，她需要计算每两个相邻元素的乘积（即 $a_1 \cdot a_2$、$a_2 \cdot a_3$，以此类推）。Iris 希望她的大脑能够安全工作，为此她希望修改数组 $a$，使得对于每个 $1 \leq i < n$，都有 $a_i \cdot a_{i+1} \leq k$。她可以进行以下两种操作： 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$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 \leq l_i < r_i \leq n$）——第 $i$ 天作业的子数组区间。 保证所有测试用例中 $n$ 的总和不超过 $10^5$，$q$ 的总和不超过 $10^5$。

对于每组测试用例，输出一行包含 $q$ 个整数，表示每一天最少需要进行多少次第 2 种操作。

在第一个测试用例中，由于 Iris 总可以将 $1$ 和 $1$ 相乘，所以不需要任何操作，因此答案为 $0$。 在第二个测试用例中，第一天的作业是 $[1, 10, 9]$。Iris 可以将其重新排列为 $[9, 1, 10]$，因此不需要进行任何第 2 种操作。第二天的作业是 $[10, 9]$，她可以将其中一个元素改为 $1$，得到 $[1, 9]$，因此需要进行一次第 2 种操作。 由 ChatGPT 4.1 翻译