The first solution is that we can find the smallest sum among at most K candidates (one for each A[i]) and
remove it. After n removes, the n-th smallest sum is found. More specifically, we can maintain K pointers for each A[i]. Let’s say ptr[1…K] (equals 1 initially). First, we can use a binary heap (or other priority queues, balanced binary search trees, etc…) to find the smallest sum among A[i] + B[ptr[i]]. Second, suppose the smallest is A[p] + B[ptr[p]]. We remove it from the heap, then increase the pointer ptr[p] by 1 and insert a new element A[p] + B[ptr[p]] if it exists. Repeat this process n times, the n-th smallest sum is got. This algorithm’s time complexity is O(n log K) for each query, and thus O(K logK + Q n logK) in total.
cany any elaborate it a little more?