公式解説と計算量は変わりませんが，高度なデータ構造を必要としない方針です． Mo’s Algorithm では差分を動的に（オンラインで）高速に求める必要がありますが，こちらの方針では差分をオフラインで求めることができれば答えも求めることができます．また，筆者の実装では fenwick tree を用いた Mo’s algorithm と本解法を比較すると fenwick tree での 加算 / 区間和取得をする回数が削減でき，実行速度も高速に動作しています．

実装例

• Mo’s algorithm + fenwick tree (Python, 4398ms)
• 本解説で紹介する解法 (Python, 3073ms)

クエリで求めたい値を \(f(x,y)\) とします．以下がオフラインで高速に求められるのとします．

• \(d_1(x,y)=f(x+1,y)-f(x.y)\)
• \(d_2(x,y)=f(x,y+1)-f(x,y)\)

（本問題では \(d_1(x,y)=\displaystyle\sum_{i=1}^y |A_{x+1}-B_i|\) であり，求めたい \((x,y)\) らを \(y\) の昇順にソートして座標圧縮と fenwick tree を用いることでまとめて求めることができます．計算量は求めたい \((x,y)\) の個数を \(q\) として \(O((N+q)\log N)\) です．）

\(B\) を \(\dfrac{N}{\sqrt{Q/2}}\) 程度の整数とします．問題を解く流れとしては以下の通りです．

1. すべての \(i,j\ (0\leq i\leq N/B, 0\leq j\leq N)\) に対して \(f(iB,j)\) を求める．これは各 \(i\) に対して \(d_2(iB,0),d_2(iB,1),\ldots\) を求めることで \(f(iB,j)=\displaystyle \sum_{k=0}^{j-1} d_2(iB,k)\) として求められる．
2. 質問 \(f(x,y)\) に対して，\(x\) 以下の最大の \(B\) の倍数を \(k\) としたときに \(f(x,y)=f(k,y)+d_1(k,y)+d_1(k+1,y)+\ldots+d_1(x-1,y)\) として求める．

以下の図も参考にしてください．
1. で求めておく \(f(x,y)\) の場所は青マス，そのために必要な \(d_2(x,y)\) の値を青矢印，2. で求めたい \(f(x,y)\) の場所を赤マス，そのために必要な \(d_1(x,y)\) の値を赤矢印で表しています．