HDU 5289 Assignment：單調隊列維護區間極值差

問題描述

給定長度 n 的數組和整數 k，求有多少個子區間滿足「最大值 - 最小值 ≤ k」。

單調隊列滑動窗口

維護兩個單調隊列：

• que1：遞增隊列，隊頭為當前窗口最小值。
• que2：遞減隊列，隊頭為當前窗口最大值。

雙指針 l, r 擴展右端點，當 max-min > k 時移動左端點 l，並從隊列中彈出下標小於 l 的元素。每次 r 移動後，以 r 為右端點的合法區間數為 r-l+1，累加即可。

代碼實現

int a[111111], qmin[111111], qmax[111111];
int main() {
    int T; scanf("%d",&T);
    while (T--) {
        int n, k; scanf("%d%d",&n,&k);
        for (int i=1;i<=n;i++) scanf("%d",&a[i]);
        int hmin=0, tmin=-1, hmax=0, tmax=-1;
        long long ans=0;
        int l=1;
        for (int r=1; r<=n; r++) {
            while (hmin<=tmin && a[qmin[tmin]]>=a[r]) tmin--;
            qmin[++tmin]=r;
            while (hmax<=tmax && a[qmax[tmax]]<=a[r]) tmax--;
            qmax[++tmax]=r;
            while (a[qmax[hmax]] - a[qmin[hmin]] > k) {
                if (qmin[hmin]==l) hmin++;
                if (qmax[hmax]==l) hmax++;
                l++;
            }
            ans += r - l + 1;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

關鍵點

• 隊列存儲下標，而非值，便於判斷是否滑出窗口。
• 彈出條件：qmin[hmin] < l 時 hmin++。
• 答案可能達 n*(n+1)/2，需 long long。

複雜度

每個元素進隊出隊各一次，時間 O(n)，空間 O(n)。

總結

HDU 5289 是「滑動窗口 + 雙單調隊列」的經典應用。關鍵在於識別「區間極值差」的單調性，並正確維護左右端點。此模板廣泛適用於「區間最大/最小值約束」的計數問題。