decremental predecessor problem
ソースコード
nachia/set/decremental-predecessor-query.hpp
主な機能
はじめ、 $A=\lbrace 0,1,\ldots ,n \rbrace$ であるとする。以下のクエリを処理する。
- 整数 $p$ $(p\lt n)$ が与えられる。 $A$ の値を $A\setminus\lbrace p\rbrace$ に更新する。
- 整数 $x\leq n$ が与えられる。 $x\leq p$ かつ $p\in A$ を満たす最小の $p$ を返す。
構造体 DecrementalPredecessorQuery
コンストラクタ
DecrementalPredecessorQuery(int _n);
- $0\leq n \leq 10^9$
- $O(n/\log n)$ 時間
初期化。
queryNoLessThan
int queryNoLessThan(int x);
- $x\lt n$
- 償却 $O(1)$ 時間、最悪 $O(\log n)$ 時間
$x\leq p$ かつ $p\in A$ を満たす最小の $p$ を返す。
dec
void dec(int p);
- $0\leq p \lt n$
- 償却 $O(1)$ 時間、最悪 $O(\log n)$ 時間
$A$ の値を $A\setminus\lbrace p\rbrace$ に更新する。