単調stack・queueによる支配候補の削除
順序に走査し、新しい要素に支配された候補を二度と必要にならないことを示して一度だけ削除する。
この典型を扱う単元: 支配関係から不要な候補を単調stack・queueで削る
検索別名: monotonic queue、monotonic stack、単調キュー、単調スタック
未知問からこの典型を見つける手掛かり
- 扱う対象
- 候補
- 次に大きい
- 次に小さい
- 窓
- 高さ
- 使う手掛かり
- pop
- 各要素を一度
- 後ろから削除
- 支配
- 次に大きい
- 保つ不変量
- stack
- 不要になった候補
- 二度と戻らない
- 単調
- 求めるもの
- nearest greater
- 区間最大
- 各prefix
- 次の要素
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: 更新可能な最小十分要約
関連する典型
学習成果と学習単位
候補を捨てられる支配条件を証明し、各候補を高々一度だけ単調stack・queueから削除できる。
支配関係から不要な候補を単調stack・queueで削るで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC213 F「Common Prefixes」 公式問題主題: 接尾辞の順序とLCPを索引化する / 補助タグ
- ABC228 F「Stamp Game」 公式問題主題: 支配関係から不要な候補を単調stack・queueで削る / 主タグ
- ABC234 G「Divide a Sequence」 公式問題主題: 支配関係から不要な候補を単調stack・queueで削る / 主タグ
- ABC248 Ex「Beautiful Subsequences」 公式問題主題: 支配関係から不要な候補を単調stack・queueで削る / 主タグ
- ABC280 Ex「Substring Sort」 公式問題主題: 接尾辞の順序とLCPを索引化する / 補助タグ
- ABC303 G「Bags Game」 公式問題主題: minimax・得点差・局面値を評価するゲームDP / 補助タグ
- ABC334 F「Christmas Present 2」 公式問題主題: DP遷移を因数分解・集約して加速する / 補助タグ
- ABC359 E「Water Tank」 公式問題主題: 支配関係から不要な候補を単調stack・queueで削る / 主タグ
- ABC379 F「Buildings 2」 公式問題主題: 支配関係から不要な候補を単調stack・queueで削る / 主タグ
- ABC420 F「kirinuki」 公式問題主題: 大小関係をCartesian treeへ変換する / 補助タグ
技能・出典
主タグ: Cartesian treeによる区間極値分解 / 補助タグ: 単調stack・queueによる支配候補の削除、累積和・差分配列
- ABC435 F「Cat exercise」 公式問題主題: 大小関係をCartesian treeへ変換する / 補助タグ
技能・出典
主タグ: Cartesian treeによる区間極値分解 / 補助タグ: DPの最小十分状態、単調stack・queueによる支配候補の削除、根付き木DP・部分木集約