hdu 3530 SubSequence TwoPoint单调队列维护最值

题意

　　一个序列 a_1,a_2,..,a_n, 求最长子序列,满足 low <= max{ai}-min{ai} <= high.

解题思路

　　首先考虑区间 [i,j], 我们可以通过固定右边界,来实现区间的滑动.以求解最佳值.

　　我们首先观察题目要求

　　　　　　low <= max{a_i,a_j}-min{a_i,a_j} <= high.

　　假定我们固定了右边界, 令 d = max{a_i,a_j} - min{a_i,a_j}

　　意味着我们只能移动 左边界i, 对于左边界的移动会导致两种情况

　　　　1. max{ a_i.a_j } 下降

　　　　2. min{ a_i, a_j } 增长

　　不管出现哪一种情形, 都将导致我们的差值d 下降.

　　意味着对于当前区间[i,j],有如下情况

　　　　1. d_{i,j} > high , 我们可以通过移动左边界i, 使差值d下降,满足要求.

　　　　2. d_{i,j} <= high && d_{i,j} < low , 此时,因为差值不满足下界,因为我们只能够减小差值d,

而无法使其增大.为了能达到这个目的,意味着我们需要一个更小的min{a_i,a_j}或者一个更大的max{a_i,a_j}.

所以这个我们可以判定这个区间包括它的子区间.

　　　　3. 满足要求时取最大.

　　对于,区间的最值,我们可以通过单调队列来实现.在本体中,单调队列只需存储下表,因为可以利用a[x],O(1)时间

得出其值.

　　　　对于单调队列的操作,无非使 插入,删除. 两种情况下的维护. 

　　　　1.插入: 从队列尾部向头部比较,找到满足要求位置,插入,并删掉从尾部到目前位置相对其小or大的值.

　　　　2.删除: 从队首向尾部比较,删除小于等于i位置之前进来的元素.

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
#define MAX(a,b) (a)>(b)?(a):(b)
const int N = 100010;

int a[N], n, low, high;

int Qmin[N], Qmax[N], f1,r1,f2,r2, ans;
 
int main(){
    
    while( scanf("%d%d%d",&n,&low,&high)!=EOF ){
        for(int i = 0; i < n; i++)
            scanf("%d", &a[i] ); 
        ans = 0;
        f1 = r1 = f2 = r2 = 0; 
        for(int i=0,j=0; j < n; j++){
            while( r1>f1 && a[Qmax[r1-1]]<=a[j] ) r1--; 
            Qmax[r1++] = j;
            while( r2>f2 && a[Qmin[r2-1]]>=a[j] ) r2--; 
            Qmin[r2++] = j;
            
            while( i<=j && (a[Qmax[f1]]-a[Qmin[f2]]>high) ){
                if( (f1<r1) && (Qmax[f1]<=i) ) f1++;
                if( (f2<r2) && (Qmin[f2]<=i) ) f2++;
                i++;    
            } 
            if( i<=j && (a[Qmax[f1]]-a[Qmin[f2]]>=low) ){
                ans = MAX( ans, j-i+1 );    
            }
        }
        printf("%d\n", ans );
    }
    return 0;    
}