I have a approach that is a bit complex, and I'm not sure if it's correct.

Square root decomposition. Precalculate ptob[i][j], meaning $$$\sum\limits_{k \in \text{block}_j} |a_k - a_i|$$$. And we will use its 2D prefix sum. Here is $$$O(n\sqrt{n})$$$.

For each query, we have two ranges: A and B, and we have some full blocks and partial blocks.

• for full(B)<->partial(A) and full(B)<->full(A), we use the result of precalculation.
• for partial(B)<->full(A), we use the result of precalculation, too.
• for partial(A)<->partial(B), it requires something else...

Consider two arrays $$$\{a\}$$$ and $$$\{b\}$$$, in order to calculate $$$\sum_{i, j} |a_i - b_j|$$$ faster than brute force, we sort both array and do something similar to merge sort. It needs we to prepare sorted result of every blocks. When queried, just filter out all the numbers we need. Additionally, it works when both A and B didn't include any full blocks.

Total time complexity is $$$O((n+q)\sqrt n)$$$

two times offline 4D Mo algo

O(n^1.75)