[hdu3530]Subsequence （单调队列）

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cstdlib>
 5 #include<iostream>
 6 #include<cmath>
 7 #define maxn 1000005
 8 using namespace std;
 9 typedef long long ll;
10 int n,m,k;
11 int qmin[maxn],qmax[maxn],a[maxn];
12 int main(){
13     while(scanf("%d%d%d",&n,&m,&k)!=EOF){
14         for(int i=1;i<=n;i++) scanf("%d",a+i);
15         int head1=0,rear1=0,head2=0,rear2=0,now=1,ans=0;
16         for(int i=1;i<=n;i++){
17             while(head1<rear1&&a[qmin[rear1-1]]>a[i]) rear1--;
18             while(head2<rear2&&a[qmax[rear2-1]]<a[i]) rear2--;
19             qmin[rear1++]=i;
20             qmax[rear2++]=i;
21             while(head1<rear1&&head2<rear2&&a[qmax[head2]]-a[qmin[head1]]>k){
22                 if(qmin[head1]<qmax[head2]) now=qmin[head1++]+1;
23                 else now=qmax[head2++]+1;
24             }
25             if(head1<rear1&&head2<rear2&&a[qmax[head2]]-a[qmin[head1]]>=m){
26                 ans=max(ans,i-now+1);
27             }
28         }
29         printf("%d\n",ans);
30     }
31 }