Blackhole and Food

Let's first assume there is just one query. How to solve that?

One option is linear search. What else?

We can sort the range in the single query then and binary search the position of K in that range. This way we get the first number equal to or larger than K. If the number is not equal to K, i;e binary search returns a number larger than K, we should check if the number right before it is closer too.

Now, how can we get all ranges sorted without sorting in each query? A data structure named merge sort tree easily does it, it's just a variation of segment tree using the basic of merge sort.

Make a segment tree on the array. In each node, keep a vector of all the numbers in that range, and keep the numbers sorted. While building the tree, you can merge the left child vector and right child vector to get current node's vector in O(N) like in merge sort. In each level of the tree, there will be n numbers in total. So, memory complexity is O(NlogN). Time complexity of building is same as merge sort, as we are basically doing merge sort with saving.

Now, for each query, we can go to the relevant node of segment tree and use binary search to find the closest number in that node. Taking the number with less index might be a bit tricky, you may want to save index number of each number while building the tree.

So overall complexity is O(Nlog(N) + Q(log(n))2).

This was the intended judge solution.

Alternate solution of Imrul vai has even better time complexity. The closest number might be smaller than K, or larger than K. Let's solve for smaller than K first.

This is similar to SPOJ KQUERY, it can be done with offline processing in O(logN) per query.

Consider each number of array as an update operation. Sort the queries and the array numbers together (the queries will be sorted based on K, if a number is equal to K of a query, keep the number first and query later).

Now, while iterating, when you come to a number, update it in the segment tree. So, when you come to a query, only the numbers small than or equal to K of this query will be in segment tree, you can just find the maximum of the range of this query then.

This way you find the closest number smaller than K, what if the closest number is larger? You can simply do the same thing again, but in reverse! Sort in descending order basically. Or you can follow what Imrul vai did, he just made all numbers negative to find this part.