BZOJ 1127 [POI2008] KUP：單調隊列優化二維子矩陣和查找

問題描述

N×N 矩陣，找一個子矩陣使其元素和在 [K, 2K] 之間。N ≤ 2000, 元素值 ≤ 2000。

核心結論

若存在元素值 ∈ [K, 2K] → 直接輸出該單元格。
否則，若存在子矩陣和 ≥ K 且所有元素 < K，則必存在子矩陣和 ∈ [K, 2K]。
證明：若和 > 2K，可逐行/列刪除直到落入區間（因單元素 < K，不會跨越區間）。

算法流程

1. 掃描矩陣，若有元素 ∈ [K, 2K] 直接輸出。
2. 將 >2K 的元素視為障礙（壞點），其餘為好點。
3. 對每行作為底，維护向上連續好點高度 h[j]。
4. 單調棧/隊列求每列作為最小高度的最大寬度矩形（經典直方圖最大矩形）。
5. 對每個極大矩形計算和（用二維前綴和 O(1)），若和 ≥ K 則輸出該矩形（並按證明縮減至 ≤2K）。
6. 若遍歷完無解，輸出 "NIE"。

關鍵代碼片段

void Monotonous_Stack(int base, int h[]) {
    // 求每列左右邊界 l[i], r[i] 使 h[i] 為最小高度
    // 計算矩形和 = Get_Sum(base-h[i]+1, l[i], base, r[i])
    // 若 >= K 輸出並縮減
}

複雜度

O(N²) — 每行單調棧 O(N)，共 N 行。N=2000 時 4×10⁶ 操作，極快。