Subsequence(Hdu3530)(单调队列运用)

题目

Hdu
Vjudge
题目大意：
给你一个长度为n的序列,让你求它的一个区间[L,R]使得区间内最大值和最小值差值在[m,k]范围内,求区间长度最大值。
范围：
$1<=n<=100000,0<=m,a[i],k<=100000$

思路

建立两个单调队列,分别维护区间最大值和最小值的位置,最大值队列中元素位置递增,值递减,最小值队列中位置递增,值递增。
处理答案时如果之差大于k，则考虑把两个队列队首相较靠前的pop掉,记录此时位置,直到满足条件,然后如果插值又满足大于m，用$i?max(last1,last2)$更新答案即可

代码

#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<queue>
#include<deque>
#include<cstdio>
#include<vector>
#include<climits>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
int read(){
    int f=1,x=0;char c=getchar();while(c<'0'||'9'<c){
    if(c=='-')f=-1;c=getchar();}while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();return f*x;
}
#define INF 0x3f3f3f3f
#define MAXN 1000000
deque<int> Q1,Q2;//1 max, 2 min
int n,m,k,a[MAXN+5];
int main(){
    while(~scanf("%d %d %d",&n,&m,&k)){
    int ans=0,last1=0,last2=0;for(int i=1;i<=n;i++)a[i]=read();Q1.clear(),Q2.clear();for(int i=1;i<=n;i++){
    while(!Q1.empty()&&a[Q1.back()]<=a[i]) Q1.pop_back();while(!Q2.empty()&&a[Q2.back()]>=a[i]) Q2.pop_back();Q1.push_back(i),Q2.push_back(i);while(a[Q1.front()]-a[Q2.front()]>k){
    if(Q1.front()<Q2.front())last1=Q1.front(),Q1.pop_front();else last2=Q2.front(),Q2.pop_front();}if(a[Q1.front()]-a[Q2.front()]>=m)ans=max(ans,i-max(last1,last2));}printf("%d\n",ans);}return 0;
}