rollback・DFS入退場の状態復元
概要
更新前の差分をstackへ記録し、分割統治・時間Segment Tree・DFSの退場時に状態を正確に巻き戻す。
考え方
更新で変わった値だけ履歴stackへ積み、checkpointまで逆順に戻す。時間区間を分割統治して入るとき追加し、出るとき戻せば、局所的な有効集合を保持できる。
DSUの履歴には、付けられる根rvの旧parent、受ける根ruの旧sizeと、更新する成分数・集約値の旧値を保存する。checkpointは履歴の現在長さh。union by sizeでrvをruへ付けるたび一記録をpushし、rollback(h)は長さhになるまでpopして旧値を代入する。同根で何も変えないunionは記録しなくてよいが、一操作一記録で取消すAPIならno-op記録が必要。checkpoint規約と混ぜない。
時間segment treeのDFSでは入場直前のhを保存し、そのnodeへ配置された全有効区間の更新を適用して子へ進み、退場時rollback(h)する。葉ではその時点を含む区間だけがroot pathへ配置されているためqueryの状態が正しく、退場後は兄弟の更新を引き継がない。
成立条件と計算量
rollback DSUでは経路圧縮を避けunion by sizeでfind O(log N)、一併合の取消O(1)。変更なしの併合もcheckpoint規約に合わせる。記録しない副作用があると元状態へ戻らない。
問題一覧
- ABC218 G「Game on Tree 2」 公式問題
技能・出典
主題: rollback・DFS入退場の状態復元(更新前の差分をstackへ記録し、分割統治・時間Segment Tree・DFSの退場時に状態を正確に巻き戻す。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: minimax・得点差・局面値を評価するゲームDP(有限DAGの局面で手番ごとの最大化・最小化と終端値を定義し、得点差や利得を後続状態から評価できる。循環時の無限継続と独立な数ゲームの加算は別の技能として扱う。) / ordered set・multisetの動的順序管理(比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: rollback・DFS入退場の状態復元 / 補助タグ: 有限局面DAGのminimax、ordered set・multisetの動的順序管理
- ABC302 Ex「Ball Collector」 公式問題組合せ: DSUによる連結成分管理・縮約
技能・出典
主題: rollback・DFS入退場の状態復元(更新前の差分をstackへ記録し、分割統治・時間Segment Tree・DFSの退場時に状態を正確に巻き戻す。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: DSUによる連結成分管理・縮約(成分へmetadataまたはmerge履歴を集約し、成分を一頂点に縮約した隣接関係、または併合後の代表情報を構成できる。)。主タグ: rollback・DFS入退場の状態復元 / 補助タグ: DSUによる連結成分管理・縮約
- ABC363 G「Dynamic Scheduling」 公式問題
技能・出典
主題: rollback・DFS入退場の状態復元(更新前の差分をstackへ記録し、分割統治・時間Segment Tree・DFSの退場時に状態を正確に巻き戻す。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 二部matching・Hall・Kőnig(二部割当が可能であることを近傍集合の大きさに関するHall条件で特徴付け、必要ならmin-cut条件と対応させられる。) / Segment Treeのcanonical区間分解(区間をO(log N)個のcanonical nodeへ分解してrange object・時間生存区間・range edgeを配置し、point queryではroot-to-leaf path上のobjectを集められる。) / 区間更新を要約へ作用させる(更新作用の合成順と要約への適用を定義し、遅延評価で保てる。)。主タグ: rollback・DFS入退場の状態復元 / 補助タグ: 二部matching・Hall・Kőnig、遅延評価する区間作用、Segment Treeのcanonical区間分解
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
前提・学習成果・出典
習得対象の目安: 青色(1600–1999)。変更前の差分を保存し、DFSや時間分割から戻るたびに不変量を復元する。
対象色の読み方は本書の読み方を参照してください。
概念上の親: 構造を共有して過去の版を保存・復元する。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-rollback
rollback・DFS入退場の状態復元
習得する技能
- 更新前の差分をstackへ記録し、分割統治・時間Segment Tree・DFSの退場時に状態を正確に巻き戻す。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: なし。
このUnitを直接前提とする単元: なし。
更新前の差分をstackへ記録し、分割統治・時間Segment Tree・DFSの退場時に状態を正確に巻き戻す。その発動条件と正当化原理を比較可能な独立教材として学ぶ。
このUnitでは扱わないもの
- rollback・DFS入退場の状態復元の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。