区間をsetで管理するやつ
Last updated：2018-04-16 03:25:49
Tweet
Category:データ構造,
Tag：
区間をsetで管理するやつ
概要
区間$[l, r]$をsetで管理する． (実装はmapだけど，”区間をsetで管理”とよく言われているため)
# 区間$[l, r]$は閉区間なので注意
次のクエリを処理する:
- $\mathrm{get}(i)$ : $i$を含む区間$[l, r]$を取得する
- $\mathrm{insert}(l, r)$ : 区間$[l, r]$を挿入する
- $\mathrm{remove}(l, r)$ : 全区間で$[l, r]$に重なる部分を全て消す
- $\mathrm{same}(i, j)$ : $i$と$j$が同じ区間に属しているかを判定する
計算量
- $\mathrm{get}$, $\mathrm{insert}$, $\mathrm{remove}$, $\mathrm{same}$: $O(\log N)$
使い方
コンストラクタへ指定するbool値は，「区間$[l, c]$と区間$[c+1, r]$をマージする」ならtrue，「マージしない」ならfalseとします．
// コンストラクタ．隣接区間をマージする
SegmentMap map(true);
// iを含む区間[l, r]のstd::map<int,int>::const_iteratorを返す, iを含む区間が無ければmap.end()を返す
auto it = map.get(i);
// 区間[l, r]を挿入する
map.insert(l, r);
// 全区間で[l, r]に重なる部分を全て消す
map.remove(l, r);
// iとjが同じ区間に属しているかのbool値を返す
bool f = map.same(i, j);
実装例