laminar区間族の包含木構築

概要

互いに素または包含関係にある区間を端点順に走査し、stackで直接包含する親を定めてdummy root付き包含木を作り、点を最小包含区間へ対応させる。

考え方

二つの区間が互いに素か包含関係になるlaminar族では、最小の包含区間を親として木・森を作れる。左端昇順、同左端なら右端降順に処理し、stackで現在の包含連鎖を保つ。

非空半開区間を左端昇順・同左端なら右端降順へsortし、同一区間を統合する。全域を覆うdummy rootをstackへ置く。区間[l,r)を読むたび、末尾の右端≤lならpopする。残った末尾pでr≤right[p]なら親をpとしてpushし、r>right[p]なら交差がありlaminar条件に反する。現在のstackは開いている包含鎖なので、末尾が直接の親となる。

点の最小包含区間は端点eventと点queryを座標順に処理して得る。同座標では終了を内側からpop、開始を外側からpush、その後点を問い合わせる(半開区間なので終了点は含めない)。stack末尾が答え、dummyならどの実区間にも属さない。二点が同じ区間側にあるかの差分は、最小包含nodeから共通祖先までの包含木pathで表せる。閉区間なら終了eventを点query後へ移し、端点で接する区間の入力規約も合わせる。

成立条件と計算量

sort O(N log N)、走査O(N)。交差する区間がないことを検査し、同一区間を一つへまとめるか別頂点にするか決める。元問題の集約値を木DPへ渡す前に、端点の開閉条件を合わせる。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

前提・学習成果・出典

習得対象の目安: 青色(1600–1999)。包含条件を確認し、端点の整列とstackで直接の親を構築する。

対象色の読み方は本書の読み方を参照してください。

概念上の親: 木構造。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-laminar-interval-containment-tree

laminar区間族の包含木構築

習得する技能

  • laminar区間の開閉端点をstackで処理し、直接包含関係と各点の最小包含区間を木として構築して、包含差分を木上pathへ変換できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: なし。

非交差区間族を括弧列として走査し、stack topを直接包含親にして包含関係を木へ変換する。その後の包含差分queryをLCAや木上距離へ接続する。

このUnitでは扱わないもの

  • laminar区間族の包含木構築の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠