HDOJ 6756 - MEXの探索
多校比赛的签到题，难度颇高。
HDOJ問題ページへのリンクリ
無向グラフ\(G=(V,E),|V|=n,|E|=m\)が与えられ、各頂点には重み\(a_i\)が設定されている。\(S_i=\{a_j\mid (i,j)\in E\}\)と定義される。支持する操作は2種類あり、\(q\)回処理する：
\(\texttt1\ x\ y)：(a_x=y)と更新する；
\(\texttt2\ x)：(\mathrm{mex}(S_x))をを求める。
\(n,m\in\left[1,10^5\righ ...
8月5日 05:01 投稿
平衡二分探索木 Treap と Splay の実装と応用
平衡二分探索木（Balanced BST）は、動的集合操作を効率よく扱うための重要なデータ構造である。特に Treap および Splay 木は、それぞれ異なる戦略で平衡性を保ちながら、挿入・削除・検索などの基本操作を平均 $O(\log n)$ 時間で実現する。
単回転 Treap
Treap（Tree + Heap）は、各ノードにランダムな優先度（priority）を持たせ、二分探索木の性質とヒープの性質を同 ...
7月24日 03:15 投稿
FHQ-Treap の学習ノート
FHQ-Treap の学習ノート
Treap は Tree と Heap を組み合わせたデータ構造です。
Treap は弱いバランスの取れた二分探索木であり、カーネルツリーとして見なせます。各ノードには (Key, Value) という2つの値を持ち、Key は二分探索木の性質を満たし、Value はヒープの性質を満たします（通常は最小ヒープ）。Key は実際の情報であり、Value はランダムな値で、木の高さが ...
6月10日 16:59 投稿
FHQ-Treapの詳細と実装：分割と併合によるランダム化平衡二分探索木
FHQ-Treap（または無旋Treap）は、ノードの回転操作を行わずに「分割」と「併合」という2つのプリミティブな操作のみを用いてバランスを維持する二分探索木です。このデータ構造は、各ノードに「値」と「ランダムな優先度」を持たせます。値は二分探索木の性質（左の子 < 親 < 右の子）を満たし、優先度はヒープの性質（親が子よりも高い優先度を持つ）を満たすよう ...
5月26日 10:16 投稿