典型タグ

端点更新型のrun分割管理

順序付きのrun分割をdequeや連結リストで保持し、両端からの削除・分割・追加を行う。左端順setを使うODTとは区別する。

この典型を扱う単元: 端点更新型のrun分割管理

検索別名: dequeによるrun管理、端点更新run分割

未知問からこの典型を見つける手掛かり

扱う対象
  • deque
  • 区間境界
  • 順序付きrun
使う手掛かり
  • 両端からrunを削る
  • 端点側で区間を分割・追加
保つ不変量
  • run順序
  • 各要素の一度限りの除去
  • 境界の復元
求めるもの
  • 操作列の償却評価
  • 端点操作によるrun分割管理
適用しない条件
個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果

分類と直接の前提

概念上の親: 更新可能な最小十分要約

    関連する典型

      学習成果と学習単位

      代表問題

      この典型の考え方を具体的な問題で確かめるための入口です。

      関連問題

      この典型が主タグまたは補助タグとして付いている問題です。