3 単調キューと単調スタック

コース内容#

問題の導入#

$RMQ (x, y)$ 関数：配列 $[x, y]$ 区間内の最小値をクエリする、参考RMQ——OI Wiki
固定されたクエリ区間の末尾を指定する場合、例えば：$RMQ (x,7)$
- 最低限、以下の 4 つの青い要素を記録すれば、$RMQ (x,7)$ のすべての要求を満たすことができる
- そしてこれらの 4 つの要素は単調増加の列を構成し、単調キューでもある
単調キューが解決するのは、このような区間の最値を維持する問題 [固定末尾の RMQ 問題]

単調キュー#

解決すべき問題の性質：スライディングウィンドウ内の区間の最値を維持する
構造定義：単調キュー
構造操作
- 入隊：まず、隊尾で単調性を破る要素を排除し、次に現在の要素を入隊する
- 出隊：もし隊首の要素がスライディングウィンドウの範囲を超えた場合、隊首が出隊する
維持の核心：隊首要素—— スライディングウィンドウ内の最値⭐
- 最小値→増加キュー
- 最大値→減少キュー
均摊時間計算量：O (1)、一度の解決
[PS] もう一つの例を挙げて印象を深める：学校が学生代表を選んで競技に参加させる
- 類似：学年 -> 配列インデックス、能力値 -> データ値、時間帯 -> スライディングウィンドウ
- 区間 [14-17] の最大値を維持する単調キューにおいて、あなたが入隊すると、赵六が排除される
  - 延伸：もしある人があなたより年齢が若く、能力もあなたより強いなら、あなたは永遠に排除される

単調スタック#

スタックとキューの違いを考えてみてください、単調スタックと単調キューの唯一の違いもここにあります、他の操作は同じです [入隊、出隊]
- 単調スタックは一方が閉じられた単調キューです
- 単調スタックは単調キューの入隊操作を保持し、依然として単調性を維持します⭐
問題の性質：最近（大きい / 小さい）関係
- 入栈の前に、単調性を満たすスタックの頂上要素が、現在の入栈要素の最近（大きい / 小さい）関係です
維持の核心：スタックの頂上要素—— 最近（大きい / 小さい）関係⭐
- 左側の最近関係→左側が先に入栈
- 右側の最近関係→右側が先に入栈
- [PS] そのスタックの底はグローバル最小値ですが、スタックで維持することには意味がありません
均摊時間計算量：O (1)、一度の解決

両者の比較#

実際、両者は主に形式が異なるだけで、本質はほぼ同じです

| |オープンポート|維持の核心|得意な問題|基本操作|
|:----:|:----|:----:|:----|:----:|:----|:----:|:----|:----|
|単調キュー| 首、尾 | 隊首 | 区間最値 | 維持単調性 + 入隊、出隊、取値|
|単調スタック| 頂 | スタックの頂上 | 最近の大小関係 | 出栈 [維持単調性]、取値、入栈 |

授業中の練習#

—— 導入 ——#

HZOJ-261：データ構造#

サンプル入力

8
I 2
I -1
I 1
Q 3
L
D
R
Q 2

サンプル出力

2
3

思考
- データ規模：$1\le N\le 1000$
- 【重要】端末のカーソル操作に類似し、カーソルの位置を維持する⭐
- 【データ構造】対頂スタック、2 つのスタック s1、s2 のスタックの頂上がカーソル位置に対応 [配列やリンクリストでもシミュレート可能]
- 【操作分析】
  - 挿入：s1 に要素を入栈
  - 削除：s1 から出栈
  - 左移動：s1 のスタックの頂上要素を s2 に移動
  - 右移動：s2 のスタックの頂上要素を s1 に移動
  - クエリ：前置和配列 sum と最大前置和配列 ans を維持し、ans に格納されているのが答え
- [PS] 単純に配列を使って実装すると、挿入が非常に時間がかかります
コード
- 新たにデータ構造を作成 -> 構造定義 + 構造操作
  - データ構造を定義した後、そのメソッドを非常に便利に使用できます
- 前置配列 sum と最大前置和配列 ans を維持するタイミング
  - s1 に要素を挿入する時：挿入操作、右移動操作
  - 削除操作、左移動操作も維持する必要がありますが、HZOJ のテストサンプルにはバグがあります：クエリ時の k 値がカーソルの現在位置 [即ち s1.size ()] を超えると、答えは 1~k の最大前置和を考慮する必要があるため、s2 の各位置に対応する最大前置和を保持する必要があります
- [PS]
  - sum、ans 配列の第 0 位には初期値を保持する必要があり、初期の前置和の累積と比較するために使用します
  - ans のデータは比較だけを担当し、計算は担当しません；sum のデータは計算だけを担当し、比較は担当しません
  - クエリ操作の入力 k が総長より大きい可能性があるため、特別に判定して、全体の最大前置和を返すこともできます

HZOJ-263：電車の進入スタック#

サンプル入力

サンプル出力

思考
- 問題文に注意：1~n が順番に進入；前 20 種類の答えを出力
- まず、サンプル出力に 312 はありますか？
  - もし最初に 3 を得たいなら、1、2 を押し込む必要があり、出栈は 321 しかできません
- 【重要】全順列の中の列が合法かどうかを判断する
- 仮定、すでに進入した最大列車番号を $x$ とし、全順列の中で現在出栈待ちの数字は $y$ である
  - もし $y ≤ x$、それは $y$ がスタックの頂上要素でなければならず、そうでなければ列は合法ではありません
  - もし $y > x$、$[x + 1,\ y]$ のすべての要素をスタックに入れる必要があり、この時スタックの頂上要素は必ず y になります
  - 例：4132、3241 が合法かどうかを判断する？
    - $x$、$y$ の比較に注意、$x$ は増加するか変わらず、減少することはありません
    - 自分でシミュレーションしてみてください
コード
- スタックの頂上ポインタと現在入栈の最大値の巧妙な利用に注意 [スタックを配列でシミュレート]
- top == -1 の判断は汎用性のためで、ここでは存在しません
- 関数bool next_permutation(begin, end)を利用して次の順列を得る [辞書順昇順]、戻り値は次の順列があるかどうかを示します
  - 参考cplusplus

—— 単調キュー ——#

HZOJ-271：スライディングウィンドウ#

サンプル入力

8 3
1 3 -1 -3 5 3 6 7

サンプル出力

-1 -3 -3 -3 3 3
3 3 5 5 6 7

思考
- データ規模：$1\le N \le 300000$
- 純粋な単調キュー、コード実装に注目
コード
- 考える：単調キューは値を記録するのか、それとも【インデックス】を記録するのか
  - インデックスを記録🆒、インデックスがあれば値を参照できます [順を追って探る]
  - 値を記録すると、逆に参照できません
- これは一般的な単調キューのテンプレートです：単調性を維持→入隊→出隊→問題に応じて出力
- 最大 / 最小値、ウィンドウのサイズに注目
- [PS] 隊尾は入隊も出隊も可能 [排除、単調性を維持]、したがって単方向キューではないと考えます

HZOJ-372：双生系列#

サンプル入力

5
3 1 5 2 4
5 2 4 3 1

サンプル出力

思考
- 考える：2 つの系列のトレンドが同じとは？
  - 同じ区間内の RMQ 値が同じである、❗ ここでの RMQ 値→最小値の最大インデックス
- 【重要】2 つの系列の各区間の RMQ 値が等しい👉2 つの系列の単調キューは同じ形をしています
  - 言い換えれば、常に 2 つの系列は対応する同じ単調キューを持っています
  - 注意：同じ形をしているとは、最小値ではなく、対応するインデックスを指します [単調キューにはインデックスが保存されています]
- 2 つの系列の要素を順次単調キューに挿入し、毎回挿入後に単調キューのサイズを比較すればよいです
  - ① 一致すれば、入隊を続ける
  - ② 一致しなければ、答えを出力する
コード
- クラスを定義して単調キューを作成し、再利用を容易にします
- 単調キューにはインデックスが保存されています：p
- 単調キュー操作：維持→入隊、出隊は必要ありません
- 【巧妙】キューのサイズの変化に基づいてトレンドの変化を把握します

HZOJ-270：最大部分和#

サンプル入力

6 4
1 -3 5 1 -2 3

サンプル出力

思考
- 部分和 → 区間和、前置和を利用して得る
- 制約条件：部分列の長さは $m$ を超えない→スライディングウィンドウ
- したがって、前置和配列の問題に変換されます
  - 目標：$max_j {s_i-s_j}\ |\ 0\lt i-j\le m$、つまり最小の $s_j$ を見つけて、$max_j {Sum_{j+1}^i}$ を得る
    - $s_i$ は元の列の前 $i$ 個の要素の和を表します
- 【問題の変換】
  - 前置和配列$s$ 上で、サイズ $m$ のスライディングウィンドウの最小値を維持します
- 👉単調キュー。注意：維持するのは元の列ではなく、前置和配列です
コード
- 単調キュー操作：出隊→取値→単調性を維持 + 入隊
  - 本来の流れは単調性を維持 + 入隊を先に行い、出隊と取値操作を後に置く [これは問題ありません]
  - しかし順序を入れ替えても問題ありません：ウィンドウサイズ $m\ge1$ なので、キューの最後の要素は少なくとも使用されないため、取値を前に置いても漏れません
  - [PS] 出隊操作は取値の前に行う必要があります
- 前置和情報だけが必要で、元の情報を配列として構築する必要はありません
- ❗ 区間和を求める際、前置和配列の 0 番目の要素の意味を忘れないでください、単調キューの初期値を必ず押し込んでおきます

—— 単調スタック ——#

HZOJ-264：最大矩形面積#

サンプル入力

7
2 1 4 5 1 3 3

サンプル出力

思考
- 考える：最大矩形の性質 ——> 矩形の高さ = 所在区域で最も低い木板の高さ x
  - 矩形の高さ > x の場合、矩形を構成できません
  - 矩形の高さ < x の場合、なぜ x と等しくできないのでしょうか？
- 具体的な思考
  - 逆に、特定の木板を現在の矩形の高さとして、左と右に向かって最初に小さい高さを探し、その間の面積がその木板が得られる最大矩形面積です
  - 各木板で得られる最大面積を遍歴し、最大値を取ります
- 求解する必要があるのは、各木板の最近の高さが小さい現在の木板の位置ですので、【単調スタック】を使用します
- [ヒント] 最適解の性質を分析することは、問題を解決する第一歩です
コード
- 必要な配列に保存するデータは：木板の高さデータ、単調増加スタック、左 / 右の最近最小を保存します
- 境界処理のテクニックに注意：両端に非常に小さい高さの木板 [-1] を設定し、スタックの底を非常に小さい高さの木板のインデックス [0、n + 1] で初期化します
- 最後に左 / 右を統合して面積を計算し、最大値を取ります
- これも一般的な単調スタックのテンプレートです：単調性を維持 [出栈] →問題に応じて取値→入栈
- サンプル解析：
  - 単調スタックに保存されているのはインデックス値であることに注意してください

ヒント#

単調キュー / スタックの動的計画法問題については、次のリンクを参照してください：2 再帰から動的計画法へ（下）