https://atcoder.jp/contests/abc255/tasks/abc255_d

ii を一つ固定した時、操作の最低回数は ∑j=1N∣Aj−Xi∣\sum_{j=1}^N |A_j-X_i| である。

AkA_k の順番は関係ないので、 AkA_k は昇順にソートしているとして良い。AkA_k をソートするのは最初に一回だけやれば良い。

累積和 Ck=∑j=1kAjC_k = \sum_{j=1}^k A_j を使って S=∑j=1N∣Aj−X∣S = \sum_{j=1}^N |A_j-X| を次のように求める。 l=max⁡{j∣Aj≤X}l = \max \{ j \mid A_j \le X\} とすると S=(lX−Cl)+((CN−Cl)−(N−l)X)S = (lX - C_l) + ((C_N-C_l) - (N-l)X) となる。

A=[1,2,4,5],X=3A = [1,2,4,5], X=3 の時、求めたいのは下の赤と青の面積で、

hist

l=2l = 2 で赤色の部分が lX−CllX - C_l, 青色の部分が (CN−Cl)−(N−l)X(C_N-C_l) - (N-l)X に対応。

各クエリに対して2分探索するところで O(log⁡N)O(\log N) 時間かかるので、O(Qlog⁡N)O(Q\log N) で全てのクエリを処理できる。

https://atcoder.jp/contests/abc255/submissions/32393722