Iris and Adjacent Products
Contest: Codeforces Round 969 (Div. 1)
Difficulty rating: 2600
Tags: data structures, greedy, implementation, math

Iris has just learned multiplication in her Maths lessons. However, since her brain is unable to withstand too complex calculations, she could not multiply two integers with the product greater than $$$k$$$ together. Otherwise, her brain may explode!

Her teacher sets a difficult task every day as her daily summer holiday homework. Now she is given an array $$$a$$$ consisting of $$$n$$$ elements, and she needs to calculate the product of each two adjacent elements (that is, $$$a_1 \cdot a_2$$$, $$$a_2 \cdot a_3$$$, and so on). Iris wants her brain to work safely, and in order to do that, she would like to modify the array $$$a$$$ in such a way that $$$a_i \cdot a_{i + 1} \leq k$$$ holds for every $$$1 \leq i < n$$$. There are two types of operations she can perform:

1. She can rearrange the elements of the array $$$a$$$ in an arbitrary way.
2. She can select an arbitrary element of the array $$$a$$$ and change its value to an arbitrary integer from $$$1$$$ to $$$k$$$.

Iris wants to minimize the number of operations of type $$$2$$$ that she uses.

However, that's completely not the end of the summer holiday! Summer holiday lasts for $$$q$$$ days, and on the $$$i$$$-th day, Iris is asked to solve the Math homework for the subarray $$$b_{l_i}, b_{l_i + 1}, \ldots, b_{r_i}$$$. Help Iris and tell her the minimum number of type $$$2$$$ operations she needs to perform for each day. Note that the operations are independent for each day, i.e. the array $$$b$$$ is not changed.

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 5\cdot 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains three integers $$$n$$$, $$$q$$$ and $$$k$$$ ($$$2 \leq n \leq 10^5$$$, $$$1 \leq q \leq 10^5$$$, $$$1 \leq k \leq 10^6$$$) — the length of array $$$b$$$, the number of days, and the upper bound for the multiplication calculation.

The second line of each test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_i \leq k$$$) — the elements of the array $$$b$$$.

Then $$$q$$$ lines follow, the $$$i$$$-th of them contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \leq l_i < r_i \leq n$$$) — the boundaries of the subarray on the $$$i$$$-th day.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$, and the sum of $$$q$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
For each test, output a single line containing $$$q$$$ integers — the minimum number of operations of type $$$2$$$ needed for each day.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first test case, as Iris can always multiply $$$1$$$ and $$$1$$$ together, no operations are needed, so the answer is $$$0$$$.

In the second test case, the first day's homework is $$$[1, 10, 9]$$$. Iris can rearrange its elements to get $$$[9, 1, 10]$$$, so no operations of type $$$2$$$ are needed. The second day's homework is $$$[10, 9]$$$, and she can change one element to get the array $$$[1, 9]$$$, so one operation of type $$$2$$$ is needed.

Example input:
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

Example output:
0 
0 1 
1 1 2 2 
1 1 1 1 0 
3 3 4 3 2 2 1 1 2 1

Editorial:
Read the hints. Let's consider how to reorder the array. Let the sorted array be $$$a_1,a_2,\dots,a_n$$$. We can prove that it is optimal to reorder it like this: $$$a_n,a_1,a_{n-1},a_2,a_{n-2},\dots$$$. You can find the proof at the end of the tutorial.
From the proof or anything we can discover the restriction is: for all $$$i$$$ that $$$1\le i\le \frac n2$$$, $$$a_i\times a_{n-i+1}\le k$$$.
Let $$$cnt(l,r)$$$ denote the number of elements with values in range $$$[l,r]$$$. We can rewrite the restrictions into: for each $$$i$$$ that $$$1\le i\le \sqrt k$$$, it must satisfy that $$$\min(cnt(1,i),\lfloor\frac n2\rfloor)\ge \min(cnt(\lfloor\frac k{i+1}\rfloor+1,k),\lfloor\frac n2\rfloor)$$$. This means that the number of $$$a_j$$$ that cannot fit $$$i+1$$$ must not be greater than the number of $$$a_j\le i$$$, and only $$$\lfloor\frac n2\rfloor$$$ numbers should be considered. Note that there're only $$$O(\sqrt k)$$$ range sums on the value range to consider, which is acceptable. Consider a modify operation, we obviously change the maximum value into $$$1$$$. This increases every $$$cnt(1,i)$$$ by $$$1$$$ and decreases every non-zero $$$cnt(\lfloor\frac k{i+1}\rfloor+1,k)$$$ by $$$1$$$, so the answer is easy to calculate. Just notice the situation when $$$cnt(1,\sqrt k)$$$ is too small and the length of the interval is too short.
How to maintain $$$cnt(1,i)$$$ for all subintervals? You can consider simply prefix sums, but its time constant factor seems too large for a 2-dimensional array. So we lowered the memory limit to reduce such issues. An easy way to handle is: solve the problem offline, and for each $$$i$$$ we calculate the prefix sum for $$$cnt(1,i)$$$ and $$$cnt(\lfloor\frac k{i+1}\rfloor+1,k)$$$, and then answer all the queries. In this way the time constant factor becomes much smaller and the memory becomes $$$O(n+q+k)$$$.
Another way to solve is to use Mo's algorithm. It uses $$$O(n+q+k)$$$ memory and $$$O(n\sqrt q)$$$ time.
The time complexity is $$$O(\sqrt k\sum(n+q))$$$.
Proof for the optimal way to reorder:
If $$$n=1$$$, it's correct.
First, it is optimal to put $$$a_n$$$ at the first position. Suppose there's a way to reorder that $$$a_n$$$ is not at the first position: $$$a_{p_1},a_{p_2},\dots,a_{p_k=n},\dots$$$, we can always reverse the prefix $$$a_{p_1},a_{p_2},\dots,a_{p_k}$$$ so that it still satisfies the condition but $$$a_n$$$ is at the first position.
Then, it is optimal to put $$$a_1$$$ at the second position. Suppose there's a way to reorder that $$$a_n$$$ is at the first position and $$$a_{t\neq 1}$$$ at the second position, as $$$a_t$$$ and $$$a_1$$$ both can fit $$$a_n$$$, we can consider them the same(any number can be put beside them), so it's possible to swap $$$a_t$$$ and $$$a_1$$$.
If $$$a_1\times a_n>k$$$, then the array isn't good. Otherwise, any number can be put beside $$$a_1$$$, so the method of reordering $$$a_2,a_3,\dots,a_{n-1}$$$ can be reduced to the same problem of $$$n'=n-2$$$. So the conclusion is proved.