# 單調佇列
單調佇列是單調性的一種運用，透過觀察在過濾掉一些不可能、或不需考慮的元素後，留下來的正好會是一個具單調性的序列時，利用其單調性來優化計算量的一種方法。
以下透過例題來理解單調佇列通常用在什麼地方，以及如何使用。
:::success
### CSES 1645 - Nearest Smaller Values
https://cses.fi/problemset/task/1645/
:::
這題的暴力解非常直覺：對每個元素往左找到第一個比自己小的元素，停下來並輸出它。
不過，考慮邪惡一點的測資：一個遞減的序列。這會導致每個元素的答案都是 $0$ 而且都必須找到底才能判斷，最糟計算量 $O(N^2)$。
順序是重要的，所以也不能排序再來二分搜尋。
### 觀察
在這題，因為答案本身就有 $N$ 個，窮舉每個元素是省不掉的。那麼，是否有辦法減少一些候補呢？
先假設每個元素必定相異（相同的情況可以等分析完再來考慮），任取兩個元素 $A_i$ 和 $A_j$，這裡 $i<j$。對於所有在 $A_j$ 右邊的元素，這兩個同時都是候補。
:::info
只要考慮好 $2$ 個元素的情況，就能推廣至任意數量的情況。
對於候補超過 $2$ 個元素的情況，可以兩兩拿出來套 $2$ 個元素時的結論。
:::
它們之間的關係只有兩種：
- $A_i<A_j$
- $A_i>A_j$
考慮第 $1$ 種情況，在 $A_i<A_k<A_j$ 時，$A_i$ 仍會是 $A_k$ 的所求，因此 $A_j$ 並不可能完全覆蓋 $A_i$ 的客群；而 $A_k>A_j>A_i$ 時會選較近的 $A_j$，所以 $A_i$ 也不可能完全覆蓋 $A_j$ 的客群。那麼兩者都有保留的必要。
考慮第 $2$ 種情形，任何可能會選到 $A_i$ 的數 $A_k>A_i$（$k>j$）基於遞移律也必定滿足 $A_k>A_j$，但是 $A_j$ 更靠近右邊的 $A_k$，所以 $A_i$ 是不可能被選上的，它的客群完全被 $A_j$ 覆蓋。
因此在 $A_j$ 出現後，$A_i$ 就不再可能是任何人的所求。可以被 $A_j$ 剔除掉。
由此結論，對任意數量的候補，只要存在任意數對 $(i, j)$ 滿足 $i<j$ 且 $A_i>A_j$，此時 $A_i$ 可被刪去而不影響後續答案。
:::info
這裡回應了前述的「只需考慮 $2$ 個元素間的情況」，就能推廣至任意數量的元素，透過任取 $2$ 個來套用 $2$ 個元素時的結論，來排除不必要的候補。
:::
刪到最後，必不存在任何數對 $(i, j)$ 滿足 $i<j$ 且 $A_i>A_j$。換句話說，對任意數對 $(i, j)$ 滿足 $i<j$ 時，一定也滿足 $A_i<A_j$，可知剩下的候補形成的序列為遞增序列，具備單調性。
:::warning
而 $A_i=A_j$ 的情況，比對會發現更接近第 $2$ 種情況：$A_i$ 客群被完全覆蓋。因此可將相等的情況歸類至第 $2$ 種情況。因此剩下的候補會是嚴格遞增序列。
:::
考慮新進的 $A_k$，對所有可能的候補可依照和 $A_k$ 之間的大小關係分成兩邊：
右邊大於等於 $A_k$ 的部份，在 $k+1$ 以後客群會被 $A_k$ 完全覆蓋，所以不再需要保留；左邊小於 $A_k$ 的部份繼續留著，且最右側的元素即為比 $A_k$ 小、又最靠近 $A_k$ 的元素，即為所求。最後將 $A_k$ 置於所求的下一個位置。
這個分界線可利用單調性進行二分搜尋，不過因為之後會刪除掉，所以直接窮舉也可以。
每個元素只會被加進候補 $1$ 次，被窮舉並移除 $1$ 次，整體的複雜度為 $O(N)$，反而比每次二分搜尋來得有效率，且易於實作。
實作上由於只會從最右邊開始移除或插入，因此使用 stack 即可維護。
```cpp=
// 因為常用到 stack 最末尾元素，定義為最後一個元素所在位置比較方便
int tail = 0;
// 用來擋 stack 為空時的特例
val[0] = -1e9;
// 需要記錄位置用來輸出
idx[0] = 0;
for (int i=1; i<=n; i++)
{
// 排除所有比 ary[i] 大的元素
for (; tail>0&&ary[i]>=val[tail]; --tail);
// 排除完後剩下都比 ary[i] 小，此時 tail 是最右邊最靠近的
ans[i] = idx[tail];
// 把 ary[i] 作為新候補塞進 stack
++tail;
val[tail] = ary[i];
idx[tail] = i;
}
```
:::success
### ZJ f174 - m6a2-蛋糕(Cake)
https://zerojudge.tw/ShowProblem?problemid=f174
:::
直觀的暴力解同樣非常單純，只要窮舉所有的區間起點，再窮舉 $1$ 到 $K$ 之間所有長度，可得 $O(NK)$ 的做法，不過顯然不夠有效率。
由於存在負數，也不能保證區間長度與區間和的關係，固定起點時的區間和也不存在單調性，反例從 sample 就能找到。
## 觀察
考慮固定區間終點 $t$ 的情況，尋找最大區間和。為了找出可用的特性，嘗試把區間和用其它方式改寫來觀察看看，例如前綴和 $S$，則所求可寫成：
$$
\max\begin{cases}
S_t-S_{t-K}\\
S_t-S_{t-K+1}\\
\ldots\\
S_t-S_{t-1}\\
\end{cases}
$$
由於 $S_t$ 固定，可以提出來：
$$
S_t-\min\begin{cases}
S_{t-K}\\
S_{t-K+1}\\
\ldots\\
S_{t-1}\\
\end{cases}
$$
問題被轉成求區間最小值，即經典 RMQ 問題，但這問題太難，所以先考慮是否有機會刪減一些候補。
## 刪減候補
考慮兩個元素 $S_i$ 和 $S_j$ 的情形，先設定 $i<j$：
- $S_i<S_j$
- $S_i>S_j$
考慮第 $1$ 種情形，平常應該要選較小的 $S_i$，但是因為 $S_i$ 比較靠左，如果到 $S_{i+K}$ 以後就取不到了，這時 $S_j$ 就算比較大，至少還是可選的。
考慮第 $2$ 種情形，$S_i$ 比較大所以不會被選中，但要等 $S_j$ 離太遠時，$S_i$ 會離更遠。所以 $S_i$ 沒有任何情況能夠被選上，$S_j$ 完全覆蓋。因此把 $S_i$ 刪掉也不影響結果。
相等的情況和第 $2$ 種情況一樣，可視為完全覆蓋。
因此，把不可能被選中的候補刪去的話，剩下的候補會是嚴格遞增序列。
和前一題不同的是，所求為最小值，而遞增序列的最小值位於最左邊。另一處不同點是左側候補有可能因為距離超過 $K$ 而被淘汰。
求遞增序列中最小值 $O(1)$，每個元素被放進單調佇列 $1$ 次，被刪去 $1$ 次，總複雜度為 $O(N)$。
實作上兩頭都會變動，因此兩頭都需要記錄。
```cpp=
// head, tail 頭尾包含
int head = 0, tail = 0, ans = 0;
val[0] = 0;
idx[0] = 0;
for (int i=1; i<=n; i++)
{
// 排除距離超過 k 的部份
if (idx[head] <= i-k)
{
++head;
}
// 遞增序列最小值即為序列最左側元素
ans = max(ans, sum[i]-val[head]);
// 排除所有比 sum[i] 大的元素 (sum 為前綴和)
for (; tail>=head&&sum[i]<=val[tail]; --tail);
// 把 sum[i] 作為新候補塞回去
++tail;
val[tail] = sum[i];
idx[tail] = i;
}
```
:::success
### TIOJ 1368 - Get High!!
https://tioj.ck.tp.edu.tw/problems/1368
:::
很直觀地窮舉所有可能的區間，可以得到一個 $O(N^2)$ 的解，但顯然不夠快。
固定終點的話，儘管序列全是正整數，區間長度越長總和越大，但區間最小值也可能更小，因此不具備單調性。
不過，考慮區間最小值不變的前提，還是具備單調性的，在此前提下區間越長越好。
因此，可以得到一個結論：最小值相同時，區間長度越長，心情就越好。
而最小值改變的前提是區間往左右擴張時，加進比目前最小值更小的值。所以對每個元素，若能找到兩邊比自己小的值中，最靠近自己的，這兩個值就各會是維持最小值不變時，左右的擴張極限。
如上圖，以塗藍色的部份為最小值時，往兩邊擴張到撞到小於自己的值為止，如圖中的藍線所示，這段區間就是這個最小值的最佳解。窮舉每個元素作為最小值，取算出來的結果最大的，即為所求。
此時問題轉為如何快速對每個最小值 $A_i$ 求左右邊界，那麼必須先找出邊界的條件。以左邊界為例，要找到左邊比自己小的數中最靠近自己的，即找到最大的 $l$ 使得 $l<i$ 且 $A_l<A_i$。
有注意到什麼嗎？沒錯，轉換後的問題和本篇講解的第一題（CSES 1645）所求一模一樣。右邊界可以用相同方式求得，或者將序列反轉後當作左邊界來求也可以。
於是得到在 $2$ 次的 $O(N)$ 求出每個最小值的最遠左、右邊界的方法，對每個最小值利用前綴和可以 $O(1)$ 算出區間的心情，整體複雜度為 $O(N)$。
### 另解
同樣考慮每個元素作為最小值的情形，對任意元素 $A_i$ 和 $A_j$ 在假定 $i<j$ 時的關係：
- $A_i<A_j$
- $A_i>A_j$
在第 $1$ 種情況，對 $A_i$ 而言，$A_j$ 不會妨礙到它往右延伸，且在當前元素 $A_k$ 處於 $A_i<A_k<A_j$ 時，$A_k$ 會被 $A_i$ 卡住但不會被 $A_j$ 卡住，所以 $A_i$ 還有被考慮的餘地，向右也還有機會延伸。
但在第 $2$ 種情況，$A_i$ 已被 $A_j$ 截斷，不可能再向右伸延；而若當前元素 $A_k>A_i$ 時，基於遞移律也會滿足 $A_k>A_j$ 所以會先被 $A_j$ 截斷，因此 $A_i$ 完全沒有任何意義，可被刪去而不影響結果。
因此只留下有意義的候補時，必為遞增序列。在加進新元素 $A_k$ 時，對於那些比 $A_k$ 大的元素 $A_j$，相當於決定了它們的右邊界，所以在刪去時可以順便結算並更新答案；直到第一個比 $A_k$ 小的元素出現時，則決定了 $A_k$ 的左邊界。
也就是說，每個元素在被加進序列時會找到左邊界，被移出序列時會決定右邊界，故移出時可順便結算。
:::warning
為了便於計算，可在最左邊加進高度 $-1$ 的元素，就不用特判如果把所有東西移除時左邊界該怎麼辦；每個元素在被移出序列時才結算，為了不在結束後還必須記得多寫一份重複的邏輯來移除剩下的元素，可在最右邊加進高度 $0$ 的元素，就會自然結算掉所有剩餘的元素。
為了不讓最右邊移除掉最左邊，所以最左用 $-1$ 最右用 $0$。這種追加原本不存在的 dummy 來簡化實作邏輯的技巧非常實用。
:::
這個做法只要 $1$ 次的 $O(N)$ 計算量，即可算出答案。
:::success
### UVa 836 - Largest Submatrix
http://domen111.github.io/UVa-Easy-Viewer/?836
:::
這題有蠻多做法能 AC 的，畢竟 $N\le 25$ 隨便做都能過。
:::danger
這題看起來沒給矩陣大小的範圍，完全是中譯的問題，切到原文就會看到很明確的規定了 $1\le N\le 25$。~~不過沒講最多幾組 test cases~~
:::
一個單純的想法是窮舉所有可能的矩陣上下界，對每個上下界窮舉每個直行是否在範圍內全都是 $1$，找到連續最多的直行，就是符合這個上下界的最大矩形。上下界 $O(N^2)$ 每個上下界窮舉所有直行 $O(N)$ 整體複雜度 $O(N^3)$。
## 問題轉換
若嘗試固定矩形下緣，找到貼著這個下緣的所有矩形最大面積，則只要窮舉 $N$ 種下緣。決定下緣後，每個直行先算出貼著此下緣的最大高度，會相當於是 $N$ 個寬度 $1$ 的矩形並排在地面上。
看起來就像這樣，是不是好像有點印象？
觀察會發現若決定將矩形左、右界定在 $[l, r]$ 則最大面積會是 $(r-l+1)\times\min(A_l, A_{l+1},\ldots,A_r)$，即寬度乘上區間內最小高度。
是不是和上一題的「區間內最小值 $\times$ 區間加總」有那麼點像？
於是發現可以套用幾乎相同的做法：在放進序列時找左界，移除時決定右界並結算，可在 $O(N)$ 的計算量，算出貼齊給定下緣的最大矩形面積。需要窮舉的下緣有 $N$ 種，總複雜度為 $O(N^2)$。
## 歡樂練習時間
:::success
### CSES 1644 - Maximum Subarray Sum II
https://cses.fi/problemset/task/1644/
:::
:::success
### TIOJ 1176 - Cows
https://tioj.ck.tp.edu.tw/problems/1176
:::
:::success
### TIOJ 1618 - 城市景觀問題
https://tioj.ck.tp.edu.tw/problems/1618
:::
:::success
### TOJ 169 - 桿杆可見度問題 II
https://toj.tfcis.org/oj/pro/169/
:::
:::success
### UVa 11488 - Hyper Prefix Sets
http://domen111.github.io/UVa-Easy-Viewer/?11488
:::
:::success
### ZJ c364 - 我鄙視你
https://zerojudge.tw/ShowProblem?problemid=c364
:::
{%hackmd @sa072686/__style %}
###### tags: `競程：二章後半`, `競程`
Sign in with Wallet
Connect another wallet