Subsequence（hdu 3530）

题意：给你一个长度为n的数列，要求一个子区间，使得区间的最大值与最小值的差s满足,
m<=s<=k，求满足条件的最长子区间

/*
  单调队列
  我们可以用单调队列分别维护最大值和最小值
  当差值大于r时要把head小的那个队列的队头弹出
  每次用合法的差值更新答案 
*/
#include<cstdio>
#include<iostream>
#include<cstring>
#define M 1000010
using namespace std;
int a[M],qmax[M],qmin[M],n,l,r;
void init()
{
    for(int i=1;i<=n;i++)
      scanf("%d",&a[i]);
    int now=1,headmax=1,headmin=1,tailmax=1,tailmin=1,ans=0;
    qmax[1]=1;qmin[1]=1;
    for(int i=2;i<=n;i++)
    {
        while(a[i]>a[qmax[tailmax]]&&headmax<=tailmax)tailmax--;qmax[++tailmax]=i;
        while(a[i]<a[qmin[tailmin]]&&headmin<=tailmin)tailmin--;qmin[++tailmin]=i;
        if(headmax<=tailmax&&headmin<=tailmin&&a[qmax[headmax]]-a[qmin[headmin]]>r)
        {
            if(qmax[headmax]>qmin[headmin]){now=qmin[headmin]+1;headmin++;}
            else {now=qmax[headmax]+1;headmax++;}
        }
        if(a[qmax[headmax]]-a[qmin[headmin]]>=l)ans=max(ans,i-now+1);
    }
    printf("%d
",ans);
}
int main()
{
    while(scanf("%d%d%d",&n,&l,&r)==3)
    {
        memset(qmax,0,sizeof(qmax));
        memset(qmin,0,sizeof(qmin));
        init();
    }
    return 0;
}