ABC 127 F - Absolute Minima

• 問題
• AC

更新クエリを$k$回処理したあとの関数を$f_k$とすると、$f_k$は

$f_k(x) = |x-a_1| + |x-a_2| + ... + |x-a_{k}| + B$

という形に書ける。$B$はクエリの定数項$b$の総和である。

以下、$(a_i)$はソート済み($a_1 \le a_2 \le ... \le a_{k}$)として考える。$x$が$a_1, a_2, ..., a_{k}$で区切られた数直線を右に進んでいくとき、$f_k(x)$の最初の傾きは$-k$であり、$a_i$を通過するたびに2ずつ増えていくので、中央値のあたりで最小値を取ることがわかる。

（ただし、この辺の理解はコンテスト後に整理したもので、コンテスト中はDesmosでグラフを描いて、真ん中あたりで最小になるというイメージを得てすぐに先に進んだ。競プロ的には常識の性質らしい。）

具体的には、偶数$k:=2n$については$x \in [a_{n}, a_{n+1}]$のときに最小値を取り、代表値として$x=a_{n}$を選ぶと

$\begin{aligned} & |x-a_1| + |x-a_2| + ... + |x-a_{2n}| \\ = & (a_{n}-a_1)+(a_{n}-a_2)+ ... + (a_{n}-a_{n}) + \\ & (a_{n+1}-a_{n})+(a_{n+2}-a_{n})+ ... +(a_{2n}-a_{n}) \\ = & -(a_1+a_2+ ... +a_{n})+(a_{n+1}+a_{n+2}+ ... +a_{2n}) \end{aligned}$

となる。奇数$k:=2n+1$については$x=a_{n+1}$のときに最小値を取り、

$\begin{aligned} & |x-a_1| + |x-a_2| + ... + |x-a_{2n+1}| \\ = & (a_{n+1}-a_1)+(a_{n+1}-a_2)+ ... + (a_{n+1}-a_{n}) + \\ & (a_{n+2}-a_{n+1})+(a_{n+3}-a_{n+1})+ ... +(a_{2n+1}-a_{n+1}) \\ = & -(a_1+a_2+ ... +a_{n})+(a_{n+2}+a_{n+3}+ ... +a_{2n+1}) \end{aligned}$

これに上の定数$B$を足せば求値クエリへの答えになる。

実装について。更新クエリ$(a, b)$を処理するにはソートされた列に（順序を保って）挿入する操作が必要になり、また求値クエリではその列の区間の和を計算しなければならない。平衡二分木ならどちらも${\mathcal O}(\log Q)$でできる。

コンテスト中にはImplicit Treapを使ったのだが、二分探索を用意するのを忘れていたのでその場で実装することになった。準備不足とも言えるけど、コンテスト中にデータ構造を多少いじること自体は避けられないと感じているので、構造に習熟しつつテスト環境を充実させる方向のほうが筋がよい気がする。

ただ、この用途で平衡二分木はややリッチすぎる気もした。真ん中で分割した2つの列にしか興味がないので、優先度付きキューを２つ使うくらいでもできるらしい。オーダーは変わらないけど……