range_set

template <class T>
struct range_set;

概要

区間をsetで管理するテク

名前	説明	計算量
`(constructor)`	空の区間集合を構築する	$O(1)$

名前	説明	計算量
`begin`	区間集合の先頭イテレータを返す	$O(1)$
`end`	区間集合の終端イテレータを返す	$O(1)$
`size`	互いに素な区間の個数を返す	$O(1)$
`length`	区間集合が覆う長さの総和を返す	$O(1)$
`get`	xを含む半開区間を返す	区間数を $q$ として $O(\log q)$
`contains`	xが区間集合に含まれるか返す	$O(\log q)$
`same`	xとyが同じ管理区間に含まれるか返す	$O(\log q)$
`insert`	(1) 半開区間を追加して連結する区間を併合する (2) 1点に対応する単位区間を追加する	(1) 併合する区間数を $k$ として $O((k+1)\log q)$ (2) $O(\log q)$
`erase`	(1) 半開区間を削除する (2) 1点に対応する単位区間を削除する	(1) 削除する区間数を $k$ として $O((k+1)\log q)$ (2) $O(\log q)$

// (1)
std::pair<T, T> insert(T x, T y);

// (2)
std::pair<T, T> insert(T x);

(1) 半開区間を追加して連結する区間を併合する

(2) 1点に対応する単位区間を追加する

// (1)
void erase(T x, T y);

// (2)
void erase(T x);

(1) 半開区間を削除する

(2) 1点に対応する単位区間を削除する