CodeChef January Lunchtime 2017: Segment Queries

https://www.codechef.com/problems/SEGMENTQ

解法

解法に入る前に簡単なゲームを考えてみよう。

n 個の箱がある。ランダムにひとつ箱を選び、その中にアメを入れておく。プレイヤーはひとつづつ箱を開けていく。もし開けた箱にアメが入っていたら、まだ開けていない箱の中からランダムにひとつ選び、その箱にアメを入れ直す。これをすべての箱を開けるまで繰り返す。

このゲームでアメを引き当てる回数の期待値は 1+1/2+1/3+\cdots+1/n である。つまり  \log n 回程度しか引き当てることはない。

解法ではこの考え方を使う。セグメントが追加されたとき、まだ mark されていない位置にアメを入れておく。点を mark したとき、そのアメに対応するセグメントをすべて調べ、アメを入れ直す。入れ直す位置がなければ、そのセグメントは無効になったと判断できる。アメを入れ直す操作の回数の期待値は O(nlogn) になるので速い。

入れ直す位置をランダムに選ぶ、という操作が地味に面倒で、真面目にやろうとすると大変である。仕方がないので RMQ を使った。