CodeChef January Lunchtime 2017: Segment Queries
https://www.codechef.com/problems/SEGMENTQ
解法
解法に入る前に簡単なゲームを考えてみよう。
n 個の箱がある。ランダムにひとつ箱を選び、その中にアメを入れておく。プレイヤーはひとつづつ箱を開けていく。もし開けた箱にアメが入っていたら、まだ開けていない箱の中からランダムにひとつ選び、その箱にアメを入れ直す。これをすべての箱を開けるまで繰り返す。
このゲームでアメを引き当てる回数の期待値は である。つまり 回程度しか引き当てることはない。
解法ではこの考え方を使う。セグメントが追加されたとき、まだ mark されていない位置にアメを入れておく。点を mark したとき、そのアメに対応するセグメントをすべて調べ、アメを入れ直す。入れ直す位置がなければ、そのセグメントは無効になったと判断できる。アメを入れ直す操作の回数の期待値は O(nlogn) になるので速い。
入れ直す位置をランダムに選ぶ、という操作が地味に面倒で、真面目にやろうとすると大変である。仕方がないので RMQ を使った。