かんプリンの学習記録

勉強したことについてメモしています. 主に競技プログラミングの問題の解説やってます.

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

感想

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