ABC370 D - Cross Explosion

いろいろな解法がある良問。基本的には集合が適宜更新されるときの mex を素早く求める問題

基本解法

壁の座標を集合で管理して、各点の右側にある壁の座標を素早く求める
- sorted set + 二分探索
- range sum セグ木 + 二分探索
  - 壁がある: 1, 壁がない: 0 として、sum = 0 かどうかの切り替わりを二分探索で求める。
- range min セグ木
  - 壁がある: 壁の座標, 壁がない: +∞ とすると、range min で右側の壁の座標が求まる
各点の右側にある壁の座標を持つ
- range update 双対セグ木
  - 壁を壊したら、range update で更新していく
壁のない区間を持つ
- 区間を union find で持つ
  - 集合の集約値として座標の最大値と最小値をもたせれば、区間が表現できる
- 区間を set で持つ
  - 要素の追加・削除と mex を対数時間で処理するよ - えびちゃんの日記