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

コース内容#

問題の導入#

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

単調キュー#

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

単調スタック#

スタックとキューの違いを考えてみてください、そして単調スタックと単調キューの唯一の違いもここにあります、他の操作は同じです [入隊、出隊]
- 単調スタックは一方が塞がれた単調キューです
- 単調スタックは単調キューの入隊操作を保持し、依然として単調性を維持します⭐
問題の性質：最近（大きい / 小さい）関係
- 入栈の前に、単調性を満たすスタックの頂要素は、現在の入栈要素の最近（大きい / 小さい）関係です
維持の核心：スタックの頂要素—— 最近（大きい / 小さい）関係⭐
- 左側の最近関係→左側が先に入栈
- 右側の最近関係→右側が先に入栈
- [PS] そのスタックの底は全体の最小値ですが、スタックで維持することには意味がありません
均摊時間計算量：O (1)、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 再帰から動的計画法へ（下）