端点更新型のrun分割管理
順序付きのrun分割をdequeや連結リストで保持し、両端からの削除・分割・追加を行う。左端順setを使うODTとは区別する。
この典型を扱う単元: 端点更新型のrun分割管理
検索別名: dequeによるrun管理、端点更新run分割
未知問からこの典型を見つける手掛かり
- 扱う対象
- deque
- 区間境界
- 順序付きrun
- 使う手掛かり
- 両端からrunを削る
- 端点側で区間を分割・追加
- 保つ不変量
- run順序
- 各要素の一度限りの除去
- 境界の復元
- 求めるもの
- 操作列の償却評価
- 端点操作によるrun分割管理
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: 更新可能な最小十分要約
関連する典型
学習成果と学習単位
dequeなどの端点操作でrun分割を更新し、左右の境界からの削除・追加と各要素の償却回数を説明できる。
端点更新型のrun分割管理で学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC428 F「Pyramid Alignment」 公式問題主題: 単調進行による償却解析 / 補助タグ
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC428 F「Pyramid Alignment」 公式問題主題: 単調進行による償却解析 / 補助タグ