I got a weird heuristic solution. But I didn't know how to hack it or prove it.

So the first problem is that if q=1, there's a greedy way to sort the p array, and for every line segment put the left end point on the left end point that's not covered.

Let's start with D[i]=1. The answer is clearly n.

And then increment D[i]. If we want the answer to change, then we just need to increase D[i] to the smallest difference among all the current points.

Then you do a brute force reconstruction for each point where the difference is equal to the minimum. If the reconstructed point overlaps with the original point, then break and reconstruct the next point equal to the minimum.

I guess it's n log^2n + q log n.

I’m not sure if this fits, but…

If $$$q = 1$$$, you can just sort the $$$p$$$ array, and greedily put the left most point of the segment on the left most point you haven't covered yet. The complexity is $$$O(ans * \log n)$$$, the implementation is very simple, you just spam upper_bound.

Now, if $$$1 \leq q \leq 10^{5}$$$, we won't be answering queries straight away. We'll call $$$T[i]$$$, $$$1 \leq i \leq n$$$, the minimum $$$l$$$ such that all point can be covered with no more than $$$i$$$ segment of length $$$l$$$. To get the answer for each $$$T[i]$$$, we can simply binary search to find the answer, then we can answer each query in $$$O(\log n)$$$ using the array $$$T$$$.

The complexity of this algorithm is $$$O(n * (\log n)^{2} * \log (max (D)) + q * \log n)$$$, because for each $$$i$$$, it takes $$$O(i * \log n * \log (max (D)))$$$ to find $$$T[i]$$$, therefore the total number of operation is $$$ (1 + 2 + 3 + ... + n) * \log n * \log (max (D))$$$ = $$$n * (\log n)^{2} * \log (max (D))$$$. To answer the query, you just have to binary search on $$$T$$$, so the complexity is $$$q * \log n$$$

Note that it is important that you set the lower bound of the binary search for each $$$1 \leq i < n$$$ to be $$$T[i + 1]$$$, as the solution depends on the fact that the complexity to check a given $$$l$$$ is $$$O(ans * \log n)$$$, and we don't want $$$ans$$$ to wander above $$$i$$$.

The complexity is really big, but I think that you can apply some heuristic tricks to make the $$$\log$$$ constant much smaller to barely fits through the constraints. Edit: sorry, had a brainfart, my solution was wrong

Here's an algorithm with $$$O(n\sqrt{q}\log n)$$$ running time, which is unlikely to pass but is at least faster than brute force.

We process the queries in increasing length order. Say the current length is $$$\ell$$$. Maintain a dynamic forest, where the parent of a point $$$p$$$ is its successor when executing the greedy algorithm (i.e., the first point after $$$p$$$ that has distance $$$>\ell$$$). Using this dynamic forest, we can simulate each step of greedy in $$$O(\log n)$$$ time.

The issue is this dynamic forest will change a lot. To handle this issue, we only update the parent of a node $$$p$$$ if there are only $$$\leq b$$$ points between $$$p$$$ and its parent, where $$$b$$$ be a parameter to be set later. Otherwise we say $$$p$$$ is "corrupted" and do not explicitly maintain its parent. In this way, the parent of a node will only change $$$O(b)$$$ times. This part overall takes $$$O(nb\log n)$$$ time.

On the other hand, there's a greedy algorithm that runs in $$$O(\mathrm{ans}\log n)$$$ time (repeatedly find the successor). Similar to this idea, we repeatedly find the next corrupted node $$$q$$$ that the greedy algorithm will encounter, which takes $$$O(\log n)$$$ time using dynamic forest, and then find the parent of $$$q$$$ by 1D successor search in $$$O(\log n)$$$ time. There will be only $$$O(\frac{n}{b})$$$ corrupted node in the optimal solution, so each query takes $$$O(\frac{n}{b}\log n)$$$ time. Balancing the terms, set $$$b=\sqrt{q}$$$, the total running time is $$$O(n\sqrt{q}\log n)$$$.