BZOJ-1047: [HAOI2007]理想的正方形（单调队列

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1047

单调队列扫一遍就可以了。。。

代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <deque>
 
using namespace std ;
 
#define MAXN 1010
 
int a , b , n , v[ MAXN ][ MAXN ] ;
 
struct Queue {
        struct node {
               int pos , val ;
               node ( int _pos , int _val ) : pos( _pos ) , val( _val ) {
               }
        };
        deque< node > Q ;
        
        void Init(  ) {
               Q.clear(  ) ;
        }
        void Add( int pos , int val , bool ( *cmp )( int x ,int y ) ) {
               while ( ! Q.empty(  ) && cmp( val , ( *( -- Q.end(  )) ).val ) ) Q.pop_back(  ) ;
               Q.push_back( node( pos , val ) ) ;
        }
        void maintain( int pos ) {
               for ( ; Q.front(  ).pos < pos ; Q.pop_front(  ) ) ;
        }
        int Query(  ) {
               return Q.front(  ).val ;
        }
} qmax , qmin ;
 
bool cmpmax( int x , int y ) {
        return x >= y ;
}
bool cmpmin( int x , int y  ) {
        return x <= y ;
}
 
int w[ MAXN ][ MAXN ][ 2 ] ;
 
int main(  ) {
        scanf( "%d%d%d" , &a , &b , &n ) ;
        for ( int i = 0 ; i ++ < a ; ) for ( int j = 0 ; j ++ < b ; ) scanf( "%d" , &v[ i ][ j ] ) ;
        for ( int i = 0 ; i ++ < a ; ) {
               qmax.Init(  ) , qmin.Init(  ) ;
               for ( int j = 0 ; j ++ < n ; ) qmax.Add( j , v[ i ][ j ] , cmpmax ) , qmin.Add( j , v[ i ][ j ] , cmpmin ) ;
               w[ i ][ 1 ][ 0 ] = qmax.Query(  ) , w[ i ][ 1 ][ 1 ] = qmin.Query(  ) ;
               for ( int j = n ; j ++ < b ; ) {
                       qmax.maintain( j - n + 1 ) , qmin.maintain( j - n + 1 ) ;
                       qmax.Add( j , v[ i ][ j ] , cmpmax ) , qmin.Add( j , v[ i ][ j ] , cmpmin ) ;
                       w[ i ][ j - n + 1 ][ 0 ] = qmax.Query(  ) , w[ i ][ j - n + 1 ][ 1 ] = qmin.Query(  ) ;
               }
        }
        int ans = 0x7fffffff ;
        for ( int i = 0 ; i ++ < b - n + 1 ; ) {
               qmax.Init(  ) , qmin.Init(  ) ;
               for ( int j = 0 ; j ++ < n ; ) qmax.Add( j , w[ j ][ i ][ 0 ] , cmpmax ) , qmin.Add( j , w[ j ][ i ][ 1 ] , cmpmin ) ;
               ans = min( ans , qmax.Query(  ) - qmin.Query(  ) ) ;
               for ( int j = n ; j ++ < a ; ) {
                       qmax.maintain( j - n + 1 ) , qmin.maintain( j - n + 1 ) ;
                       qmax.Add( j , w[ j ][ i ][ 0 ] , cmpmax ) , qmin.Add( j , w[ j ][ i ][ 1 ] , cmpmin ) ;
                       ans = min( ans , qmax.Query(  ) - qmin.Query(  ) ) ;
               }
        }
        printf( "%d\n" , ans ) ;
        return 0 ;
}