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