题解 P3512 【[POI2010]PIL-Pilots】

· · 题解

n<=3000000，单调队列。

因为要同时维护最大值和最小值，所以需要两个单调队列，记录序号和最大最小值，然后

从左往右枚举一遍O(n)的复杂度即可。

单调队列的实现以最大值为例，当队列非空且队尾的数没有现在枚举到的这个数大时，就

让队尾的数出队，因为在接下来的情况中它们永远不会是一个区间的最大值。最小值的队列同理。把当前位置加入最大最小值队列。然后比较最大值队列的队首即最大值和最小值，如果它们的差超过了k，就看一下最大值和最小值的队首哪个的序号更小，让序号更小的出队，同时更新当前队列的最前节点的位置，继续比较两个的队首，直到最大最小值的差小于等于k时，用当前位置减去当前队列的最前节点的位置再加一，就是目前的符合条件的序列长度，与最长值比较即可。

当前队列的最前节点的位置初始值为1.

代码如下：

#include<iostream>
#include<cstdio>
using namespace std;
#define ll long long
ll k,n,a[3000005],q_mx[3000005],q_mn[3000005];
ll head_mx,head_mn,tail_mx,tail_mn,len,pre;
int main(){
//    freopen("1.in","r",stdin);
    scanf("%lld%lld",&k,&n);
    len=0;
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    q_mx[1]=1;q_mn[1]=1;pre=1;
    head_mx=1;tail_mx=1;head_mn=1;tail_mn=1;
    for(int i=2;i<=n;i++){
        while(head_mx<=tail_mx&&a[q_mx[tail_mx]]<a[i])tail_mx--;
        while(head_mn<=tail_mn&&a[q_mn[tail_mn]]>a[i])tail_mn--;
        q_mx[++tail_mx]=i;q_mn[++tail_mn]=i;
        while(a[q_mx[head_mx]]-a[q_mn[head_mn]]>k){
            if(q_mx[head_mx]<q_mn[head_mn]){pre=q_mx[head_mx]+1;head_mx++;}
            else {pre=q_mn[head_mn]+1;head_mn++;}
        }
        //pre=min(q_mx[head_mx],q_mn[head_mn]);
        len=max(len,i-pre+1);
    }
    printf("%lld",len);
}