区間をsetで管理するテク 実装メモ

毎回迷うのでライブラリにする。いわゆるinterval setってやつ。

サポートすること

• 区間の追加・マージ
  • 区間の増分を返す
• 区間の削除
  • 区間の減分を返す
• ある地点xが区間に覆われているか？
• 今覆われている区間の長さの和

実装

あくまでinterval setなので、重なる区間は常にマージする。

計算量は今覆われている区間の長さの和が$O(1)$、それ以外のクエリ回数を$Q$として$O(Q\log Q)$になる…はず。

bookmark

verify

• 区間をsetで管理するやつ(簡単) - mojacoder

bookmark