hdu 3530 dp + 單調隊列優化

題目：http://acm.hdu.edu.cn/showproblem.php?pid=3530

題意：給你一個長度為n的數列，要求一個子區間，使得區間的最大值與最小值的差s滿足,

m<=s<=k，求滿足條件的最長子區間

分析：做了前面幾題後，這題容易想到用兩個單調隊列維護目前最值，

作為判斷條件，如果內插補點大于k了，就去掉較前面的那個隊列元素，并把區間頭更新為它的标号+1，

這裡注意內插補點小于m并不需要去掉元素，還有更新答案時要先判斷是否滿足條件才能更新，

/**/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<memory.h>
using namespace std;
const int maxn=100002;
int qmin[maxn],qmax[maxn],n,m,k,a[maxn];
int main()
{
    while(~scanf("%d%d%d",&n,&m,&k))
    {
        int i,j,l=0,ans=0;
        int lm=0,lx=0,rm=0,rx=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            while(lm<rm&&a[qmin[rm-1]]>a[i]) rm--;
            while(lx<rx&&a[qmax[rx-1]]<a[i]) rx--;
            qmin[rm++]=i;
            qmax[rx++]=i;
            while(a[qmax[lx]]-a[qmin[lm]]>k)
            {
                l=(qmin[lm]<qmax[lx]?qmin[lm++]:qmax[lx++]);//WA 了n 次。。。
            }
            if(a[qmax[lx]]-a[qmin[lm]]>=m)
            {
                ans=max(ans,i-l);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}
/*
5 0 0
1 1 1 1 1
5 0 3
1 2 3 4 5
8 0 3
1 2 3 4 6 5 5 5
10 0 3
1 5 8 7 2 2 2 3 5 2
*/