Educational Codeforces #95 D Trash Problem - かんプリンの学習記録

問題概要
思考の流れ
提出プログラム
感想

問題概要

数直線上の ${x_i(1\leq i\leq N)}$ の位置にあるゴミを2つ以下の座標に集める. 1回の操作につき, 座標 ${x}$ にあるゴミをまとめて ${x+1}$ か ${x-1}$ に移動させることができる. 最小の操作回数を求めよ. また, ある座標へのゴミの追加や削除クエリが ${Q}$ 個与えられるのでそれぞれのクエリ後の最小操作回数も求めよ.

${1\leq N,Q\leq 10^5\\ 0\leq x_i\leq 10^9}$

思考の流れ

集める2か所の決め方を考える. 集めるゴミは区間になっていることは簡単にわかる. 左側の1か所に集めるゴミのindexを ${1\leq i\leq k}$ , 右側の1か所に集めるゴミのindexを ${k+1\leq i\leq N}$ とすると, 最小操作回数は ${x_k-x_1+x_N-x_{k+1}}$ となる. ${x_N-x_1-(x_{k+1}-x_k)}$ となるので, これを最小とするには ${x_{k+1}-x_k}$ を最大とする ${k}$ を求めればいいことがわかる.

${\downarrow}$

追加・削除のクエリ後に ${x_{k+1}-x_k}$ の最大値を求められればいい. 追加・削除・最大値取得ができるデータ構造といえば, 平衡二分木などがある. ちょうどC++のsetの機能で実現できるので解ける.

追加クエリでは追加する座標を ${x_p}$ とすると, ${x_p}$ と隣り合ったゴミの座標 ${x_{p+1},x_{p-1}}$ をもとめてsetに ${x_{p+1}-x_p}$ , ${x_p-x_{p-1}}$ を追加し, 今まであった ${x_{p+1}-x_{p-1}}$ を消せばよい. 削除クエリも同様に行う.

提出プログラム

https://codeforces.com/contest/1418/submission/93091660

感想

問題読み間違えて中央値求めるアレかと思った.