标签：单调队列
Description
Tz又耍畸形了！！他要当飞行员，他拿到了一个飞行员测试难度序列，他设定了一个难度差的最大值，在序列中他想找到一个最长的子串，任意两个难度差不会超过他设定的最大值。耍畸形一个人是不行的，于是他找到了你。
Input
输入：第一行两个有空格隔开的整数k（0<=k<=2000,000,000），n(1<=n<=3000,000)，k代表Tz设定的最大值，n代表难度序列的长度。第二行为n个由空格隔开的整数ai（1<=ai<=2000,000,000），表示难度序列。
Output
输出：最大的字串长度。
Sample Input
3 9
5 1 3 5 8 6 6 9 10
Sample Output
4
（有两个子串的长度为4: 5, 8, 6, 6 和8, 6,6, 9.最长子串的长度就是4）
分析：
这题一开始想着用一个队列乱搞，过了半小时搞不出来
看hzwer的博客才发现要维护两个单调队列
和NOIP2016D2T2蚯蚓那题很相像（用三个队列的结论题）
对于此题，考虑每个右端点，它符合题意的左端点序号一定是单调递增的
所以可以用两个单调队列来做，一个保证递增，另一个保证递减
这样我们每次选取两个队列的队头，它们之间的差值一定是最大的，如果不符合题意那么把其中位置靠前的一个队头出队，以此更新答案
Code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif
using namespace std;
inline ll read()
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=3e6+6;
int l1,r1,l2,r2,ans=0,k,n,a[maxn],t,q1[maxn<<1],q2[maxn<<1];
int main()
{
k=read(),n=read();
rep(i,1,n)a[i]=read();
l1=l2=r1=r2=1;
rep(i,1,n){
while(l1<=r1&&a[i]>=a[q1[r1]])r1--;//维护单调下降的队列
while(l2<=r2&&a[i]<=a[q2[r2]])r2--;//维护单调上升的队列
q1[++r1]=i,q2[++r2]=i;
while(a[q1[l1]]-a[q2[l2]]>k)
if(q1[l1]<q2[l2])t=q1[l1++];
else t=q2[l2++];
ans=max(ans,i-t);
}
cout<<ans<<endl;
return 0;
}
