支配関係から不要な候補を単調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順にはこの償却原理を流用できない。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 水色(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。

根拠