えびちゃんの日記

えびちゃん(競プロ)の日記です。

2023-11-22から1日間の記事一覧

ポインタ木なしで償却 O(log(n)²) 時間の predecessor query

お風呂で思いついたシリーズです。 できる操作は次の通りです。 $\texttt{new}()$ $∅$ で初期化する $S.\texttt{insert}(x)$ $S ← S ∪ \{x\}$ で更新する $S.\texttt{remove}(x)$ $S ← S \smallsetminus \{x\}$ で更新する $S.\texttt{less}(a)$ $\max {\{x∈…