問題はこちら
問題概要
個の半開区間の和集合を求めよ.解説
以下のように半開区間の集合に新たに半開区間を追加することを考えます.このような追加を高速に行うことができれば解くことができそうです.
既に集合に含まれる区間と追加する区間が重なっていなければそのまま追加すればいいだけですが,重なっている場合はうまく処理する必要があります.
具体的には,追加する区間を,集合内の区間をの昇順に並べたときの番目の区間をとしたとき,集合内のと重なる区間のうち一番左の区間が,一番右の区間がであれば,を削除します.その後,を「のとのの小さい方」,を「のとのの大きい方」としたときのを集合に追加すれば区間の和集合を求めることができます.
を高速に求められれば良いですが,これはstd::setなどのlower_boundを用いると可能になります.くわしくは実装を見てください.