laminar区間族の包含木構築
互いに素または包含関係にある区間を端点順に走査し、stackで直接包含する親を定めてdummy root付き包含木を作り、点を最小包含区間へ対応させる。
この典型を扱う単元: laminar区間族の包含木構築
検索別名: interval containment tree、laminar family tree、laminar区間包含木、区間包含木
未知問からこの典型を見つける手掛かり
- 扱う対象
- containment parent
- dummy root
- laminar intervals
- opening and closing endpoints
- 使う手掛かり
- 包含関係をqueryで再利用
- 区間同士が非交差
- 点を最小包含区間へ写す
- 保つ不変量
- open intervals form one ancestor stack
- stack top is direct parent
- subtree equals containment
- 求めるもの
- 包含木構築
- 区間queryの木上path化
- 適用しない条件
- 交差する一般区間のoverlap graph
- 値の大小から作るCartesian tree
分類・前提・学習成果
分類と直接の前提
概念上の親: 木モデルと構造
関連する典型
学習成果と学習単位
laminar区間の開閉端点をstackで処理し、直接包含関係と各点の最小包含区間を木として構築して、包含差分を木上pathへ変換できる。
laminar区間族の包含木構築で学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC405 F「Chord Crossing」 公式問題主題: laminar区間族の包含木構築 / 主タグ
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC405 F「Chord Crossing」 公式問題主題: laminar区間族の包含木構築 / 主タグ