\(\displaystyle f(X,Y)=\sum_{i=1}^X \sum_{j=1}^Y |A_i-B_j|\) とします。

この問題は Mo’s Algorithm (クエリ平方分割 ) と呼ばれるアルゴリズムを用いることで効率的に解くことができます。 Mo’s Algorithm の概要は以下の通りです：

• 適当な値 \(M\) を設定する。
• \(\displaystyle \left\lfloor \frac{X_k}{M} \right\rfloor\) が同じ値となるようなクエリを一つのブロックにまとめる。
• 各ブロックに対して以下の操作を行う：
  • ブロック内で \(Y_k\) の昇順にソートする。
  • ブロック内の各クエリに対して順番に直前のクエリの答えからの答えの差分を求めることで答えを求める。

この問題で \(f(X+1,Y)-f(X,Y)\) と \(f(X,Y+1)-f(X,Y)\) がどちらも \(O(\alpha)\) で計算できると仮定した場合、上のアルゴリズムの計算量は \(\displaystyle O\left(\max\left(MK\alpha,\frac{N^2\alpha}M\right)\right)\) となります。 \(\displaystyle M=O\left(\frac{N}{\sqrt K} \right)\) と設定することで、計算量を \(O\left(N\sqrt K\alpha \right)\) にすることができます。Mo’s algorithm に関するより詳しい説明は、以下の記事などを参考にしてください。

Mo’s algorithm - アルゴリズムとデータ構造大全

Mo’s algorithm - ei1333の日記

以下は \(f(X+1,Y)-f(X,Y)\) と \(f(X,Y+1)-f(X,Y)\) を高速に計算する方法について考えます。

\(B_1,B_2,\ldots,B_{Y}\) のうち \(A_{X+1}\) 未満であるものの個数と総和をそれぞれ \(C,S\) とすると、

\[ \begin{aligned} \displaystyle f(X+1,Y)-f(X,Y)&=\sum_{j=1}^Y |A_{X+1}-B_j|\\ &=\sum_{j=1}^Y\left( A_{X+1}+B_j-2\min(A_{X+1},B_j) \right)\\ &=YA_{X+1}+\sum_{j=1}^Y B_j -2\left\{(Y-C)A_{X+1}+S \right\} \end{aligned} \]

となります。ここで、この \(C\) と \(S\) の値は座標圧縮と fenwick tree を組み合わせることで求めることができます。詳しい実装方法は下の実装例などを参考にしてください。

以上を適切に実装することで本問題は計算量 \(O(N\sqrt{K}\log N)\) で解くことができます。

実装例 (Python3)

from atcoder.fenwicktree import FenwickTree

n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
q = int(input())
query = []
for i in range(q):
    x, y = map(int, input().split())
    query.append((x, y, i))
w = 1000
query.sort(key=lambda x: (x[0] // w, x[1] if (x[0] // w) % 2 == 0 else -x[1]))

s = sorted(list(set(A + B)))
d = {}
sz = len(s)
for i in range(sz):
    d[s[i]] = i
a = [d[i] for i in A]
b = [d[i] for i in B]

fta0 = FenwickTree(sz)
fta1 = FenwickTree(sz)
ftb0 = FenwickTree(sz)
ftb1 = FenwickTree(sz)

ans = [0] * q
x = 0
y = 0

now, asum, bsum = 0, 0, 0

for xi, yi, i in query:
    while x < xi:
        c = ftb0._sum(a[x])
        s = ftb1._sum(a[x])
        now += y * A[x] + bsum - 2 * ((y - c) * A[x] + s)
        asum += A[x]
        fta0.add(a[x], 1)
        fta1.add(a[x], A[x])
        x += 1
    while x > xi:
        x -= 1
        c = ftb0._sum(a[x])
        s = ftb1._sum(a[x])
        now -= y * A[x] + bsum - 2 * ((y - c) * A[x] + s)
        asum -= A[x]
        fta0.add(a[x], -1)
        fta1.add(a[x], -A[x])
    while y < yi:
        c = fta0._sum(b[y])
        s = fta1._sum(b[y])
        now += x * B[y] + asum - 2 * ((x - c) * B[y] + s)
        bsum += B[y]
        ftb0.add(b[y], 1)
        ftb1.add(b[y], B[y])
        y += 1
    while y > yi:
        y -= 1
        c = fta0._sum(b[y])
        s = fta1._sum(b[y])
        now -= x * B[y] + asum - 2 * ((x - c) * B[y] + s)
        bsum -= B[y]
        ftb0.add(b[y], -1)
        ftb1.add(b[y], -B[y])
    ans[i] = now

print(*ans, sep="\n")

実装例(C++)

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <atcoder/all>

using namespace std;
using ll = long long;

int main() {
    int n;
    cin >> n;
    vector<ll> A(n), B(n);
    for (int i = 0; i < n; i++) cin >> A[i];
    for (int i = 0; i < n; i++) cin >> B[i];

    int q;
    cin >> q;
    vector<tuple<int, int, int>> query(q);
    for (int i = 0; i < q; i++) {
        int x, y;
        cin >> x >> y;
        query[i] = {x, y, i};
    }

    int w = 1000;
    sort(query.begin(), query.end(), [w](const auto& a, const auto& b) {
        int block_a = get<0>(a) / w;
        int block_b = get<0>(b) / w;
        if (block_a != block_b) return block_a < block_b;
        return (block_a % 2 == 0) ? (get<1>(a) < get<1>(b)) : (get<1>(a) > get<1>(b));
    });

    vector<ll> s(A.begin(), A.end());
    s.insert(s.end(), B.begin(), B.end());
    sort(s.begin(), s.end());
    s.erase(unique(s.begin(), s.end()), s.end());

    map<ll, int> d;
    int sz = s.size();
    for (int i = 0; i < sz; i++) d[s[i]] = i;

    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) a[i] = d[A[i]];
    for (int i = 0; i < n; i++) b[i] = d[B[i]];

    atcoder::fenwick_tree<ll> fta0(sz), ftb0(sz);
    atcoder::fenwick_tree<ll> fta1(sz), ftb1(sz);

    vector<ll> ans(q);
    int x = 0, y = 0;
    ll now = 0, asum = 0, bsum = 0;

    for (const auto& [xi, yi, i] : query) {
        while (x < xi) {
            ll c = ftb0.sum(0, a[x] + 1);
            ll s = ftb1.sum(0, a[x] + 1);
            now += y * A[x] + bsum - 2 * ((y - c) * A[x] + s);
            asum += A[x];
            fta0.add(a[x], 1);
            fta1.add(a[x], A[x]);
            x++;
        }
        while (x > xi) {
            x--;
            ll c = ftb0.sum(0, a[x] + 1);
            ll s = ftb1.sum(0, a[x] + 1);
            now -= y * A[x] + bsum - 2 * ((y - c) * A[x] + s);
            asum -= A[x];
            fta0.add(a[x], -1);
            fta1.add(a[x], -A[x]);
        }
        while (y < yi) {
            ll c = fta0.sum(0, b[y] + 1);
            ll s = fta1.sum(0, b[y] + 1);
            now += x * B[y] + asum - 2 * ((x - c) * B[y] + s);
            bsum += B[y];
            ftb0.add(b[y], 1);
            ftb1.add(b[y], B[y]);
            y++;
        }
        while (y > yi) {
            y--;
            ll c = fta0.sum(0, b[y] + 1);
            ll s = fta1.sum(0, b[y] + 1);
            now -= x * B[y] + asum - 2 * ((x - c) * B[y] + s);
            bsum -= B[y];
            ftb0.add(b[y], -1);
            ftb1.add(b[y], -B[y]);
        }
        ans[i] = now;
    }

    for (const auto& res : ans) cout << res << "\n";

    return 0;
}