支配関係から不要な候補を単調stack・queueで削る
概要
単調stack・queueによる支配候補の削除
順序に走査し、新しい要素に支配された候補を二度と必要にならないことを示して一度だけ削除する。
考え方
新しい候補より今後常に不利な候補を末尾から除く。stackでは次の大きい要素、dequeではwindow内の最小・最大などを扱い、支配されない候補だけを順序つきで保つ。
window最小ではindexをdequeへ値の非減少順に持つ。右端iを追加するとき、末尾jでa[j]≥a[i]の間popしてからiをpushする。iはjより新しく値も小さいので、今後iを含むwindowでjが最小候補へ戻ることはない。左端Lを動かしたら先頭index<Lをpopし、非空なら先頭値を答えにする。左端・右端がともに非減少という条件が削除の安全性を与える。
次に大きい要素を求めるstackでは、未回答indexを値の非増加順に持つ。新値a[i]が末尾a[j]より大きい間popし、jの答えをiとする。それまでの全位置では大きい値を見つけなかったためiが最初の答えとなる。最後にiをpushし、終了後の未回答は無しとする。≥を探す場合はpop条件も≥へ変える。
成立条件と計算量
各要素が一度pushされ一度popされるためO(N)。同値を残すか消すかは左端・右端の優先や数え上げによる。dequeでは範囲外の先頭削除も必要。任意のquery順にはこの償却原理を流用できない。
問題一覧
- ABC359 E「Water Tank」 公式問題
技能・出典
主題: 支配関係から不要な候補を単調stack・queueで削る(候補を捨てられる支配条件を証明し、各候補を高々一度だけ単調stack・queueから削除できる。)。 - ABC379 F「Buildings 2」 公式問題
技能・出典
主題: 支配関係から不要な候補を単調stack・queueで削る(候補を捨てられる支配条件を証明し、各候補を高々一度だけ単調stack・queueから削除できる。)。 - ABC228 F「Stamp Game」 公式問題
技能・出典
主題: 支配関係から不要な候補を単調stack・queueで削る(候補を捨てられる支配条件を証明し、各候補を高々一度だけ単調stack・queueから削除できる。)。既習技能: 一次元・二次元累積和と差分で区間情報を線形化する(prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。)。主タグ: 単調stack・queueによる支配候補の削除 / 補助タグ: 累積和・差分配列
- ABC234 G「Divide a Sequence」 公式問題組合せ: prefix分割DP
技能・出典
主題: 支配関係から不要な候補を単調stack・queueで削る(候補を捨てられる支配条件を証明し、各候補を高々一度だけ単調stack・queueから削除できる。)。既習技能: prefix分割DP(列の最後のブロックを固定し、処理済みprefixの答えから次の切れ目へ遷移する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 単調stack・queueによる支配候補の削除 / 補助タグ: prefix分割DP
- ABC248 Ex「Beautiful Subsequences」 公式問題組合せ: 区間monoid要約、区間更新を要約へ作用させる
技能・出典
主題: 支配関係から不要な候補を単調stack・queueで削る(候補を捨てられる支配条件を証明し、各候補を高々一度だけ単調stack・queueから削除できる。)。既習技能: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。) / 区間更新を要約へ作用させる(更新作用の合成順と要約への適用を定義し、遅延評価で保てる。)。主タグ: 単調stack・queueによる支配候補の削除 / 補助タグ: 遅延評価する区間作用、区間monoid要約
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC213 F「Common Prefixes」 公式問題主題: 接尾辞の順序とLCPを索引化する
技能・出典
主題: 接尾辞の順序とLCPを索引化する(接尾辞の辞書順とLCPを索引化し、出現範囲・部分文字列順位・distinct数・巡回shiftを処理できる。)。既習技能: 支配関係から不要な候補を単調stack・queueで削る(候補を捨てられる支配条件を証明し、各候補を高々一度だけ単調stack・queueから削除できる。)。主タグ: 接尾辞順序・LCP索引 / 補助タグ: 単調stack・queueによる支配候補の削除
- ABC280 Ex「Substring Sort」 公式問題主題: 接尾辞の順序とLCPを索引化する
技能・出典
主題: 接尾辞の順序とLCPを索引化する(接尾辞の辞書順とLCPを索引化し、出現範囲・部分文字列順位・distinct数・巡回shiftを処理できる。)。既習技能: 支配関係から不要な候補を単調stack・queueで削る(候補を捨てられる支配条件を証明し、各候補を高々一度だけ単調stack・queueから削除できる。)。主タグ: 接尾辞順序・LCP索引 / 補助タグ: 単調stack・queueによる支配候補の削除
- ABC303 G「Bags Game」 公式問題
技能・出典
主題: minimax・得点差・局面値を評価するゲームDP(有限DAGの局面で手番ごとの最大化・最小化と終端値を定義し、得点差や利得を後続状態から評価できる。循環時の無限継続と独立な数ゲームの加算は別の技能として扱う。)。既習技能: 支配関係から不要な候補を単調stack・queueで削る(候補を捨てられる支配条件を証明し、各候補を高々一度だけ単調stack・queueから削除できる。)。主タグ: 有限局面DAGのminimax / 補助タグ: 単調stack・queueによる支配候補の削除
- ABC334 F「Christmas Present 2」 公式問題
技能・出典
主題: DP遷移を因数分解・集約して加速する(素朴な遷移元の列挙をprefix・suffix・区間の和や極値へ書き換え、依存順と問い合わせ範囲を保って高速化できる。)。既習技能: 支配関係から不要な候補を単調stack・queueで削る(候補を捨てられる支配条件を証明し、各候補を高々一度だけ単調stack・queueから削除できる。)。 配達の直接経路をbaselineにし、補充境界iの追加費用をd_iとする。dp[i]=d_i+min_{i−K≤j<i}dp[j]。窓から出た候補と支配される候補をdequeから除き、O(NK)をO(N)へ落とす。主タグ: DP遷移の集約・高速化 / 補助タグ: 単調stack・queueによる支配候補の削除
- ABC420 F「kirinuki」 公式問題
技能・出典
主題: 大小関係をCartesian treeへ変換する(配列順とheap順を保つCartesian treeを単調stackで構成し、各部分木が表す連続区間へ問題を分解できる。)。既習技能: 一次元・二次元累積和と差分で区間情報を線形化する(prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。) / 支配関係から不要な候補を単調stack・queueで削る(候補を捨てられる支配条件を証明し、各候補を高々一度だけ単調stack・queueから削除できる。)。主タグ: Cartesian treeによる区間極値分解 / 補助タグ: 単調stack・queueによる支配候補の削除、累積和・差分配列
- ABC435 F「Cat exercise」 公式問題
技能・出典
主題: 大小関係をCartesian treeへ変換する(配列順とheap順を保つCartesian treeを単調stackで構成し、各部分木が表す連続区間へ問題を分解できる。)。既習技能: 根付き木DP・部分木集約(根付き木で子側の状態を合成し、部分木または木全体の値を求められる。) / 最小十分状態からDPを設計する(採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。) / 支配関係から不要な候補を単調stack・queueで削る(候補を捨てられる支配条件を証明し、各候補を高々一度だけ単調stack・queueから削除できる。)。主タグ: Cartesian treeによる区間極値分解 / 補助タグ: DPの最小十分状態、単調stack・queueによる支配候補の削除、根付き木DP・部分木集約
前提・学習成果・出典
習得対象の目安: 水色(1200–1599)。将来不要な候補を削る支配関係と、一要素一度の償却計算量を説明する。
対象色の読み方は本書の読み方を参照してください。
概念上の親: データ構造と問い合わせ。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-monotone-stack-queue
習得する技能
- 候補を捨てられる支配条件を証明し、各候補を高々一度だけ単調stack・queueから削除できる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: なし。
このUnitを直接前提とする単元: 大小関係をCartesian treeへ変換する。
候補の支配関係を証明し、不要になった要素を一度だけ捨てて線形処理へ変える。
このUnitでは扱わないもの
- 全候補から極値を反復取得するheap・ordered set。