ABC127 F. Absolute Minima
問題
関数f(x)があり、はじめはf(x)=0として与えられる。
Q個のクエリが与えられ、
- 更新クエリの場合は、f(x) <- f(x) + |x-a|+b
- 求値クエリの場合は、f(x)の最小値とその時のxを出力
を行え。
制約
- 1 <= Q <= 2*10^5
- -10^9 <= a, b <= 10^9
- 1番目のクエリは更新クエリ
解法
与えられた問題は、「min Σ |x-a_i| + b_i」を求める問題と言い換えられる。
ここでb_iは与えられるたびに加算していけば良いので、結局は
min Σ |x-a_i|
をa_iが与えられるたびに高速に求められれば良い。
この答えは、xが「与えられたa_iの中央値」のとき最小値となる。
中央値を高速に管理する手段として、multisetを2つl,r持って、
- lに値を入れる
- lよりもrのサイズが2以上大きければlの最大の値をrに移す(サイズを均等にする)
- lの最大値とrの最大値を比較し、大小関係が逆であれば入れ替える(状態を維持)
というのを繰り返せば、lの最大値が常に中央値になる。
最小にするxがlの最大値で得られるので、そのx_minに対してΣ|x-a_i|を求めることを考える。
x_minより小さいa_iについてはΣ(x-a_i)で、x_minより大きいa_iについてはΣ(a_i-x)となる。
これは、lとrで管理できているので、multisetと一緒に、入っている値の和l_sum, r_sumを一緒に管理しておけば、「(lのサイズ*x_min - lsum) + (rsum - rのサイズ*x_min)」で求められる。
したがって、最終的な答えは、これにΣb_iを足したものになる。
