ブロックサイズを \(Q\) とします。

\(\displaystyle 1 \le i \le N, 1 \le j \le \lfloor \frac{N}{Q} \rfloor\) に対して \(\displaystyle C_{i,j}=\sum_{k=1}^i \sum_{l=1}^{jQ} |A_k - B_l|\) 、\(\displaystyle 1 \le i \le \lfloor \frac{N}{Q} \rfloor, 1 \le j \le N\) に対して \(\displaystyle D_{i,j}=\sum_{k=1}^{iQ} \sum_{l=1}^{j} |A_k-B_l|\) を求めます。これらは、二分探索と累積和によって効率的に求められます。

このとき、各クエリで求める値は \(\displaystyle C_{X,\lfloor \frac{Y}{Q} \rfloor}+D_{\lfloor \frac{X}{Q} \rfloor,Y}-C_{\lfloor \frac{X}{Q} \rfloor \times Q,\lfloor \frac{Y}{Q} \rfloor}+\sum_{i=\lfloor \frac{X}{Q} \rfloor \times Q+1}^X \sum_{j=\lfloor \frac{Y}{Q} \rfloor \times Q+1}^Y |A_i-B_j|\) となります。

計算量は \(\displaystyle O(\frac{N}{Q} (Q+N \log Q)+K Q^2)\) です。

実装例 (C++, Q=350, 2951ms): https://atcoder.jp/contests/abc384/submissions/60789613