https://atcoder.jp/contests/abc255/tasks/abc255_d
\(i\) を一つ固定した時、操作の最低回数は \(\sum_{j=1}^N |A_j-X_i|\) である。
\(A_k\) の順番は関係ないので、 \(A_k\) は昇順にソートしているとして良い。\(A_k\) をソートするのは最初に一回だけやれば良い。
累積和 \(C_k = \sum_{j=1}^k A_j\) を使って \(S = \sum_{j=1}^N |A_j-X|\) を次のように求める。 \(l = \max \{ j \mid A_j \le X\}\) とすると \(S = (lX - C_l) + ((C_N-C_l) - (N-l)X)\) となる。
\(A = [1,2,4,5], X=3\) の時、求めたいのは下の赤と青の面積で、
\(l = 2\) で赤色の部分が \(lX - C_l\), 青色の部分が \((C_N-C_l) - (N-l)X\) に対応。
各クエリに対して2分探索するところで \(O(\log N)\) 時間かかるので、\(O(Q\log N)\) で全てのクエリを処理できる。