HDU 5089 Assignment：RMQ+二分與單調隊列求合法區間數

題目大意

給定長度 n 的數組 a[1..n] 和整數 k。若區間 [l, r] 滿足：最大值 - 最小值 < k，則稱為合法區間。求合法區間總數。n ≤ 1e5，多測試用例。

方法一：RMQ + 二分

• 預處理 O(n log n) 構建稀疏表，O(1) 查詢區間最值。
• 對每個左端點 i，二分最大右端點 r 使 max(i,r) - min(i,r) < k。區間數累加 r - i + 1。
• 總複雜度 O(n log n)。

方法二：單調隊列（滑動窗口） - O(n)

• 維護兩個單調隊列：遞減隊列存最大值候選，遞增隊列存最小值候選。
• 雙指針 l, r 擴展右端點。若當前窗口 max - min ≥ k，移動左端點 l 並彈出隊首過期元素。
• 每次 r 移動後，以 r 為右端點的合法區間數為 r - l + 1，累加即可。
• 需注意：題目要求「差值 < k」，故判斷條件為 max - min >= k 時縮窗。

單調隊列核心代碼

int mique[N], maque[N], mihead, mahead, mitail, matail;
ll ans = 0;
int now = 1, pre = 0;
for (int i = 1; i <= n; i++) {
    // 入隊 a[i]
    while (mihead < mitail && a[i] <= a[mique[mitail-1]]) mitail--;
    mique[mitail++] = i;
    while (mahead < matail && a[i] >= a[maque[matail-1]]) matail--;
    maque[matail++] = i;
    // 縮窗直到合法
    while (a[maque[mahead]] - a[mique[mihead]] >= k) {
        int outPos = min(mique[mihead], maque[mahead]) + 1;
        // 計算新增合法區間數：等差數列求和技巧
        // ... (見原代碼)
        if (mique[mihead] < maque[mahead]) mihead++; else mahead++;
        now = outPos;
    }
    ans += i - now + 1;
}

總結

單調隊列為線性最優解，適合大數據。RMQ+二分代碼較短，常數稍大但易理解。本題為經典「滑動窗口統計合法子區間」模型。