Chopping Carrots (Hard Version)
Contest: Codeforces Round 809 (Div. 2)
Difficulty rating: 2400
Tags: brute force, constructive algorithms, data structures, dp, greedy, math, number theory, two pointers

This is the hard version of the problem. The only difference between the versions is the constraints on $$$n$$$, $$$k$$$, $$$a_i$$$, and the sum of $$$n$$$ over all test cases. You can make hacks only if both versions of the problem are solved.

Note the unusual memory limit.

You are given an array of integers $$$a_1, a_2, \ldots, a_n$$$ of length $$$n$$$, and an integer $$$k$$$.

The cost of an array of integers $$$p_1, p_2, \ldots, p_n$$$ of length $$$n$$$ is $$$$$$\max\limits_{1 \le i \le n}\left(\left \lfloor \frac{a_i}{p_i} \right \rfloor \right) - \min\limits_{1 \le i \le n}\left(\left \lfloor \frac{a_i}{p_i} \right \rfloor \right).$$$$$$

Here, $$$\lfloor \frac{x}{y} \rfloor$$$ denotes the integer part of the division of $$$x$$$ by $$$y$$$. Find the minimum cost of an array $$$p$$$ such that $$$1 \le p_i \le k$$$ for all $$$1 \le i \le n$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_1 \le a_2 \le \ldots \le a_n \le 10^5$$$).

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

Output format:
For each test case, print a single integer — the minimum possible cost of an array $$$p$$$ satisfying the condition above.

Constraints:
Time limit: 4.0 s
Memory limit: 64.0 MB

Note:
In the first test case, the optimal array is $$$p = [1, 1, 1, 2, 2]$$$. The resulting array of values of $$$\lfloor \frac{a_i}{p_i} \rfloor$$$ is $$$[4, 5, 6, 4, 5]$$$. The cost of $$$p$$$ is $$$\max\limits_{1 \le i \le n}(\lfloor \frac{a_i}{p_i} \rfloor) - \min\limits_{1 \le i \le n}(\lfloor \frac{a_i}{p_i} \rfloor) = 6 - 4 = 2$$$. We can show that there is no array (satisfying the condition from the statement) with a smaller cost.

In the second test case, one of the optimal arrays is $$$p = [12, 12, 12, 12, 12]$$$, which results in all $$$\lfloor \frac{a_i}{p_i} \rfloor$$$ being $$$0$$$.

In the third test case, the only possible array is $$$p = [1, 1, 1]$$$.

Example input:
7
5 2
4 5 6 8 11
5 12
4 5 6 8 11
3 1
2 9 15
7 3
2 3 5 5 6 9 10
6 56
54 286 527 1436 2450 2681
3 95
16 340 2241
2 2
1 3

Example output:
2
0
13
1
4
7
0

Editorial:
Solution 1
Let's fix $$$v$$$, the minimum value of $$$\lfloor \frac{a_i}{p_i} \rfloor$$$. Then, for all $$$1 \le i \le n$$$, we find the maximum value $$$p_i$$$ such that $$$p_i \le k$$$ and $$$\lfloor \frac{a_i}{p_i} \rfloor \ge v$$$.
For some minimum value $$$v$$$, let's call the array described above $$$P(v)$$$, and let's define $$$M(v) = \max\limits_{1 \le i \le n} \lfloor \frac{a_i}{P(v)_i} \rfloor$$$. We can find the answer by taking the minimum of $$$M(v) - v$$$ across all $$$0 \le v \le a_1$$$, giving a $$$O(n \cdot a_i)$$$ solution.
To speed it up, let's consider how some element $$$a_i$$$ will affect the values of $$$M(v)$$$.
First, notice that $$$\lfloor \frac{a_i}{q} \rfloor$$$ (where $$$1 \le q \le k$$$) can take on at most $$$O(\min(k,\sqrt{a_i}))$$$ distinct values. Let's denote these values (in increasing order) $$$s_1, s_2, s_3, \ldots, s_x$$$. Consider what happens when $$$v \le s_1$$$. Then, $$$M(v)$$$ must be at least $$$s_1$$$. What about when $$$s_1 < v \le s_2$$$? Then, $$$M(v)$$$ must be at least $$$s_2$$$. And so on, until $$$s_{x - 1} < v \le s_x$$$, where $$$M(v)$$$ must be at least $$$s_x$$$.
This way, we can get lower bounds on value of $$$M(v)$$$. It is easy to see that the highest of these bounds is achievable.
Let's iterate over array $$$a$$$. Let $$$m[v]$$$ (here, $$$m = m[0], m[1], m[2], \ldots, m[a_1]$$$ is an array of length $$$a_1 + 1$$$) be the highest of lower bounds on $$$M(v)$$$ we already found. Initially, $$$m[v] = 0$$$ for all $$$v$$$. When we are dealing with $$$a_i$$$ we want to do the following:
• For all $$$0 \le j \le x - 1$$$, we want to update $$$m[y] = \max(m[y], s_{j+1})$$$ for all $$$s_{j} + 1 \le y \le s_{j + 1}$$$ (for convenience we define $$$s_0 = -1$$$).
Since $$$s_0 < s_1 < s_2 < \ldots < s_x$$$, this can be done without any fancy data structures — instead of updating all these ranges directly, we can set $$$m[s_j + 1] = \max(m[s_j + 1], s_{j+1}])$$$, so that $$$M(v)$$$ will be equal to $$$\max(m[0], m[1], \ldots, m[v])$$$.
Then, once $$$m$$$ is computed, we can sweep through to find all values of $$$M(v)$$$ in with prefix maxes.
Once we have $$$m$$$ computed, we can find $$$M(v) - v$$$ for all $$$0 \le v \le a_1$$$ in linear time. This gives a $$$\mathcal{O}(\sum\limits_{1 \le i \le n}\min(k, \sqrt{a_i}) + a_1)$$$ solution per test case, with total $$$\mathcal{O}(n + \max_a)$$$ memory across all tests.
Solution 2 (AlperenT)
Now, let's fix $$$v$$$ as the maximum value of $$$\lfloor \frac{a_i}{p_i} \rfloor$$$. We now want to maximize the minimum value of $$$\lfloor \frac{a_i}{p_i} \rfloor$$$.
Let's now consider all elements $$$a_i$$$ that satisfy $$$1 \le a_i \le v$$$. For these elements, it will be optimal to set $$$p_i = 1$$$, since we want to maximize them.
How about elements $$$a_i$$$ satisfying $$$v + 1 \le a_i \le 2(v+1) - 1$$$? We need to have $$$\lfloor \frac{a_i}{p_i} \rfloor \le v$$$, so for these elements, we must have $$$p_i \ge 2$$$. At the same time, we want to maximize them  — so it will be optimal to set all these $$$p_i = 2$$$.
Continuing this logic, for all integers $$$u = 1, 2, \ldots, k$$$, we should check the elements $$$a_i$$$ satisfying $$$(u-1)\cdot (v + 1) \le a_i \le u \cdot (v+1)$$$, and set all these $$$p_i = u$$$.
How can we determine the minimum value of $$$\lfloor \frac{a_i}{p_i} \rfloor$$$ from this? For a fixed $$$u$$$, the minimum $$$\lfloor \frac{a_i}{u} \rfloor$$$ will come from the minimum $$$a_i$$$. So if we can determine the minimum $$$a_i$$$ such that $$$(u-1)\cdot (v + 1) \le a_i \le u \cdot (v+1)$$$, and calculate these values across all $$$u = 1, 2, \ldots, k$$$, then we will get the answer.
To help us, let's precompute an array $$$next_1, next_2, \ldots, next_{a_n}$$$. $$$next_j$$$ will store the minimum value of $$$a_i$$$ such that $$$a_i \ge j$$$. Now, for a fixed $$$u$$$, we can check $$$next_{(u-1) \cdot v + 1}$$$. If this value is less than or equal to $$$u \cdot v$$$, it will be the minimum $$$a_i$$$ that we divide by $$$u$$$.
Two important details:
1. If there exists some $$$a_i \ge (v + 1) \cdot k$$$, then it is impossible to have the max element as $$$v$$$, and we should skip it.
2. For some value $$$v$$$, we only need to check $$$u$$$ such that $$$(u-1)\cdot v + 1 \le a_n$$$.
Using this second detail, the solution runs in $$$\mathcal{O}\left( \sum\limits_{i = 1}^{a_n}\frac{a_n}{i} \right) = \mathcal{O}(a_n \cdot \log(a_n))$$$ time per test case. The memory usage is $$$\mathcal{O}(n + \max_a)$$$ across all tests.