hdu 3530 Subsequence(单调队列)

#include  
#include  
#include  
using namespace std ;  
  
const int maxn = 111111 ;  
int n , m , num[maxn] , k ;  
struct Deque {  
    int val[2][maxn], pos[2][maxn];  
    int star[2] , tail[2] ;  
    void init () {  
        star[0] = 1 ;  
        tail[0] = 0 ;  
        star[1] = 1 ;  
        tail[1] = 0 ;  
    }  
    int judge (int c, int v) {  
        return c ^ (val[c][tail[c]] < v);  
    }  
    void push (int id, int v) {  
        int i ;  
    //  printf ( "id = %d , v = %d\n" , id , v ) ;  
        for ( i = 0 ; i < 2 ; i ++ ) {  
            while ( star[i] <= tail[i] && judge ( i , v ) )  
                tail[i] -- ;  
            val[i][++tail[i]] = v ;  
            pos[i][tail[i]] = id ;  
        }  
    }  
    void pop ( int c ) {  
        if ( star[c] <= tail[c] ) star[c] ++ ;  
    }  
    int gao ( int &last ) {  
        while ( (val[0][star[0]] - val[1][star[1]] >





 k ) ) {  
            if ( pos[1][star[1]] < pos[0][star[0]] ) {  
                last = pos[1][star[1]] ;  
                pop ( 1 ) ;  
            }  
            else {  
                last = pos[0][star[0]] ;  
                pop ( 0 ) ;  
            }  
        }  
        if ( val[0][star[0]] - val[1][star[1]] < m ) return -1 ;  
        return last ;  
    }  
} q ;  
  
int main () {  
    int i , j ;  
    while ( scanf ( "%d%d%d" , &n , &m , &k ) != EOF ) {  
        for ( i = 1 ; i <= n ; i ++ )  
            scanf ( "%d" , &num[i] ) ;  
        q.init () ;  
        int ans = 0 , last = 0 ;  
        for ( i = 1 ; i <= n ; i ++ ) {  
            q.push ( i , num[i] ) ;  
            int k = q.gao ( last ) ;  
            if ( k == -1 ) continue ;  
            last = k ;  
            ans = max ( ans , i - last ) ;  
        }  
        printf ( "%d\n" , ans ) ;  
    }  
    return 0 ;  
}