問題重述

N 個袋子排成一排，第 i 個袋子有 a[i] 顆糖果。對於每個窗口長度 x (1≤x≤N)，考慮所有長度為 x 的連續子區間，取區間最大值，再取所有區間最大值的最小值作為答案。輸出 x=1..N 的答案。

樣例：1 3 2 4 5 → 輸出 1, 3, 3, 4, 5。

核心洞察

對於固定位置 i，其值 a[i] 能作為區間最大值的條件是：區間內無比 a[i] 大的元素。即向左擴展到第一個 > a[i] 的位置，向右同理。得到最大區間 [L, R]，則長度 1 .. R-L+1 的所有區間都能以 a[i] 為最大值（取包含 i 的子區間）。

因此，對每個長度 len，答案是所有滿足 R_i - L_i + 1 ≥ len 的 a[i] 的最小值。

算法流程

1. RMQ 預處理：ST 算法 O(N log N) 構建，O(1) 查詢區間最大值。
2. 對每個 i 二分邊界：
   • 左邊界：在 [1, i] 中找最左位置 L 使 max(L, i) ≤ a[i]。
   • 右邊界：在 [i, N] 中找最右位置 R 使 max(i, R) ≤ a[i]。
3. 線段樹維護長度最小值：
   • 區間更新：對長度區間 [1, R-L+1] 取最小值 a[i]。
   • 單點查詢：最終對每個 len=1..N 查詢答案。

關鍵代碼片段

// RMQ ST 表
int dp[N][20], lg[N];
void build_st() {
    for (int i=1;i<=n;++i) dp[i][0]=a[i];
    for (int j=1;j<=lg[n];++j)
        for (int i=1;i+(1<>1;
    if (R<=mid) update(p<<1, L, R, v);
    else if (L>mid) update(p<<1|1, L, R, v);
    else update(p<<1, L, mid, v), update(p<<1|1, mid+1, R, v);
    tr[p].val=min(tr[p<<1].val, tr[p<<1|1].val);
}

複雜度

• RMQ 構建：O(N log N)
• N 次二分：O(N log N) × O(1) 查詢 = O(N log N)
• 線段樹 N 次區間更新 + N 次查詢：O(N log N)
• 總體：O(N log N)，N ≤ 100000 輕鬆通過。

易錯點

1. 二分邊界條件：max ≤ a[i] 而非 <，因相等時最大值仍為 a[i]。
2. 線段樹初始值設為 INF，懶標記初始 -1 表示無標記。
3. 多測試用例需重置全局數組與 lg 表。

總結

本題巧妙結合「單調棧思想（二分邊界）」與「線段樹區間取最小」，將「每個長度的最小最大值」轉化為「每個元素貢獻的長度區間」。RMQ 提供 O(1) 區間最大值查詢，使二分可行；線段樹高效合併所有元素的貢獻。這是「區間極值統計」類問題的經典組合拳。