[POI2010]PIL-Pilots 单调队列

[POI2010]PIL-Pilots

题意：

给定一个序列和一个数值k，求一段连续最大区间是的最大值与最小值之差小于k；

思路：

因为要维护最大值和最小值并且连续，使用两个单调队列分别同时维护最大最小值；

细节：

因为算最大区间长度，并且要弹出两个队列值较小的，所以用下标维护更方便；

代码

#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

const int N=3e6+7;

int k,n,ans;

int a[N];

int q1[N],q2[N],l = 1, h1=1,t1=0,h2=1,t2=0;

int main(){

	scanf("%d%d",&k,&n);

	for(int i=1;i<=n;i++) scanf("%d",&a[i]);

	for(int i=1;i<=n;i++){

		while(t1>=h1&&a[i]>a[q1[t1]]) t1--;

		q1[++t1]=i;

		while(t2>=h2&&a[i]<a[q2[t2]]) t2--;

		q2[++t2]=i;

		while(abs(a[q1[h1]]-a[q2[h2]])>k){

			if(q1[h1]<q2[h2]) l=q1[h1]+1,h1++;

			else l=q2[h2]+1,h2++;

		}

		ans=max(ans,max(q1[t1],q2[t2])-l+1);

	}

	cout<<ans;

}