問題はこちら
問題概要
数直線上のの位置にあるゴミを2つ以下の座標に集める. 1回の操作につき, 座標にあるゴミをまとめてかに移動させることができる. 最小の操作回数を求めよ. また, ある座標へのゴミの追加や削除クエリが個与えられるのでそれぞれのクエリ後の最小操作回数も求めよ.思考の流れ
集める2か所の決め方を考える. 集めるゴミは区間になっていることは簡単にわかる. 左側の1か所に集めるゴミのindexを, 右側の1か所に集めるゴミのindexをとすると, 最小操作回数はとなる. となるので, これを最小とするにはを最大とするを求めればいいことがわかる.
追加・削除のクエリ後にの最大値を求められればいい. 追加・削除・最大値取得ができるデータ構造といえば, 平衡二分木などがある. ちょうどC++のsetの機能で実現できるので解ける.
追加クエリでは追加する座標をとすると, と隣り合ったゴミの座標をもとめてsetに,を追加し, 今まであったを消せばよい. 削除クエリも同様に行う.