ABC127 F - Absolute Minima - ツバサの備忘録

解法

$B_{i}$ は、とりあえず答えに加算すれば良いので、ほとんど無視して問題ないです。ということで、 $A_{i}$ と $x$ について考えていきます。
$|x-A_{i}|$ の総和を最小化する問題は、 $x$ を $A_{i}$ の中央値にすればよいです。現在の $x$ がわかっているとき、 $x \lt A_{i}$ となるような $A_{i}$ については $|x-A_{i}| = A_{i} - x$ 、そうでないときは $|x-A_{i}| = x - A_{i}$ となります。
中央値を計算する際、必要なのは中央値に近い部分のみです。ということで、 $x$ より大きい部分と、そうでない部分で2つに分割し、ちょうど中間あたりのみを見ることができるようにします。
ここで登場するのが優先度付きキューです。2つ使用します。
$A_{i}$ について、値が小さいものについては降順に取り出すことができる優先度付きキューに、値が大きいものについては昇順に取り出すことができる別の優先度付きキューに格納すると、真ん中に近い部分が、2つのキューの先頭に現れます。
あとは、次に追加される $A_{i}$ と、2つのキューの先頭を見比べ、2つのキューが矛盾しないかつ、サイズの差が常に1以下になるように調整していけば、キューの先頭がちょうど中央値、 $x$ になります。
$f(x)$ の出力は、2つのキューの総和をあらかじめ求めておいて(キューの更新は要素を1つずつに対してのみなので、要素を入れたり出したりするたびに総和も更新しておけばよいです)、絶対値の計算の定義に合うように調整をします。小さい値が入っているキューの総和を-1倍すればよいです。その後、2つのキューの総和、 $B_{i}$ の総和と、奇数の場合は $x$ を合わせて計算(小さいキューのサイズが大きい時は $x$ を加算、そうでないときは減算)すれば、答えが求まります。