Split the arrays \(a,b\) into blocks of size \(B\).

We first calculate \(va_{i,j}\) for all blocks \(i\) and all positions \(j\). This value stands for \(\sum_{x\in\text{block}_i}|a_x-b_j|\). This can be calculated by sorting all elements in the \(i\)-th block and the \(b\) array beforehand, and use two pointers to maintain this value. Similarly we can define \(vb_{i,j}\) as the total contribution between the \(i\)-th block of \(b\) and the \(j\)-th element of \(a\).

For a query, we can split the first \(x\) elements of \(a\) into \(O(\frac nB)\) whole blocks and \(O(B)\) elements in another block. We do the same with the first \(y\) elements of \(b\). Then:

1. For the whole blocks of \(a\), we simply use \(va\) to calculate the contribution to the answer (it can be done in \(O(1)\) per query by prefix sum).

2. For the other \(O(B)\) elements of \(a\), we first use \(vb\) to calculate the contribution between them and the whole blocks of \(b\). Then we only have \(O(B)\) elements left in both \(a\) and \(b\), we can simply sort them and scan them from small to large to calculate the answer.

However, it’s worth noticing that all the \(O(B)\) elements are from the same block. Thus we can sort the elements of every block beforehand and use two pointers to calculate the answer of the last part.

Now we analyze the complexity. For the preparation, we have \(O(\frac nB)\) blocks, where we sort every block of size \(O(B)\), and for every position calculates its \(va,vb\) in a total of \(O(n)\) time. So this part has complexity \(O(\frac nB\times (B\log B+n))=O(\frac{n^2}B)\). For each query, we calculate the answer for whole blocks in \(O(\frac nB)\) time, and \(O(B)\) time for the rest.

In all, the total complexity is \(O(\frac{n^2}B+kB)\). By choosing \(B=n\sqrt{k}\), we get the complexity \(O(n\sqrt{k})\).

Code (the fastest without constant optimization on purpose by the time of writing)