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)$ で全てのクエリを処理できる。