單調佇列

單調佇列是單調性的一種運用，透過觀察在過濾掉一些不可能、或不需考慮的元素後，留下來的正好會是一個具單調性的序列時，利用其單調性來優化計算量的一種方法。

以下透過例題來理解單調佇列通常用在什麼地方，以及如何使用。

CSES 1645 - Nearest Smaller Values

https://cses.fi/problemset/task/1645/

這題的暴力解非常直覺：對每個元素往左找到第一個比自己小的元素，停下來並輸出它。

不過，考慮邪惡一點的測資：一個遞減的序列。這會導致每個元素的答案都是

$0$ 而且都必須找到底才能判斷，最糟計算量

$O(N^2)$。

順序是重要的，所以也不能排序再來二分搜尋。

觀察

在這題，因為答案本身就有

$N$ 個，窮舉每個元素是省不掉的。那麼，是否有辦法減少一些候補呢？

先假設每個元素必定相異（相同的情況可以等分析完再來考慮），任取兩個元素

$A_i$ 和

$A_j$，這裡

$i<j$。對於所有在

$A_j$ 右邊的元素，這兩個同時都是候補。

只要考慮好

$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$ 可被刪去而不影響後續答案。

這裡回應了前述的「只需考慮

$2$ 個元素間的情況」，就能推廣至任意數量的元素，透過任取

$2$ 個來套用

$2$ 個元素時的結論，來排除不必要的候補。

刪到最後，必不存在任何數對

$(i,j)$ 滿足

$i<j$ 且

$A_i>A_j$。換句話說，對任意數對

$(i,j)$ 滿足

$i<j$ 時，一定也滿足

$A_i<A_j$，可知剩下的候補形成的序列為遞增序列，具備單調性。

而

$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 即可維護。

// 因為常用到 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;
}

ZJ f174 - m6a2-蛋糕(Cake)

https://zerojudge.tw/ShowProblem?problemid=f174

直觀的暴力解同樣非常單純，只要窮舉所有的區間起點，再窮舉

$1$ 到

$K$ 之間所有長度，可得

$O(NK)$ 的做法，不過顯然不夠有效率。

由於存在負數，也不能保證區間長度與區間和的關係，固定起點時的區間和也不存在單調性，反例從 sample 就能找到。

觀察

考慮固定區間終點

$t$ 的情況，尋找最大區間和。為了找出可用的特性，嘗試把區間和用其它方式改寫來觀察看看，例如前綴和

$S$，則所求可寫成：

$$max\{\begin{array}{l}{S}_t-S_{t-K}\\ S_t-S_{t-K+1}\\ \dots \\ S_t-S_{t-1}\end{array}$$

由於

$S_t$ 固定，可以提出來：

$$S_t-min\{\begin{array}{l}{S}_{t-K}\\ S_{t-K+1}\\ \dots \\ S_{t-1}\end{array}$$

問題被轉成求區間最小值，即經典 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)$。

實作上兩頭都會變動，因此兩頭都需要記錄。

// 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;
}

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$ 的左邊界。

也就是說，每個元素在被加進序列時會找到左邊界，被移出序列時會決定右邊界，故移出時可順便結算。

為了便於計算，可在最左邊加進高度

$-1$ 的元素，就不用特判如果把所有東西移除時左邊界該怎麼辦；每個元素在被移出序列時才結算，為了不在結束後還必須記得多寫一份重複的邏輯來移除剩下的元素，可在最右邊加進高度

$0$ 的元素，就會自然結算掉所有剩餘的元素。

為了不讓最右邊移除掉最左邊，所以最左用

$-1$ 最右用

$0$。這種追加原本不存在的 dummy 來簡化實作邏輯的技巧非常實用。

這個做法只要

$1$ 次的

$O(N)$ 計算量，即可算出答案。

UVa 836 - Largest Submatrix

http://domen111.github.io/UVa-Easy-Viewer/?836

這題有蠻多做法能 AC 的，畢竟

$N\le 25$ 隨便做都能過。

這題看起來沒給矩陣大小的範圍，完全是中譯的問題，切到原文就會看到很明確的規定了

$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},\dots ,A_r)$，即寬度乘上區間內最小高度。

是不是和上一題的「區間內最小值

$\times$ 區間加總」有那麼點像？

於是發現可以套用幾乎相同的做法：在放進序列時找左界，移除時決定右界並結算，可在

$O(N)$ 的計算量，算出貼齊給定下緣的最大矩形面積。需要窮舉的下緣有

$N$ 種，總複雜度為

$O(N^2)$。

歡樂練習時間

CSES 1644 - Maximum Subarray Sum II

https://cses.fi/problemset/task/1644/

TIOJ 1176 - Cows

https://tioj.ck.tp.edu.tw/problems/1176

TIOJ 1618 - 城市景觀問題

https://tioj.ck.tp.edu.tw/problems/1618

TOJ 169 - 桿杆可見度問題 II

https://toj.tfcis.org/oj/pro/169/

UVa 11488 - Hyper Prefix Sets

http://domen111.github.io/UVa-Easy-Viewer/?11488

ZJ c364 - 我鄙視你

https://zerojudge.tw/ShowProblem?problemid=c364

tags: 競程：二章後半, 競程