学步园

hev神让我做做这题... 

大概我们可以用一个二维的单调队列来写的。

用两个矩阵来记录大矩阵的部分最值。

例如用A[i][j]来记录mat[i][j]---mat[i+r-1][j]这一列的最小值，用Mi[i][j]来记录A[i][j]--A[i][j+c-1]这一行的最小值，于是乎Mi[i][j]就是mat[i,i+r-1][j,j+c-1]这个r*c的子矩阵的最小值了。

我的代码相当挫

大家都是530++ms AC的 我却要970ms.... 再看看别人的代码...

发现压线过特别有快感啊！

#include<iostream>
#include<string>
#include<cstdio>
#define MN 1111
#define INF 0x7F7F7F7F
#define FF(i,N) for( int i=0;i<N;i++ )
using namespace std;

int mat[MN][MN];
int A[MN][MN],B[MN][MN],Mi[MN][MN],Ma[MN][MN];
int n,m,r,c;
struct node{
   int id,v;
}mi[MN],ma[MN];
int hemi,hema;

void insert( int num,int y )
{
 	 while( y-mi[hemi].id>=r&&mi[hemi].v!=INF ) hemi++;
 	 while( y-ma[hema].id>=r&&ma[hema].v!=INF ) hema++;
 	 int i;
 	 for( i=hemi;mi[i].v!=INF;i++ )
 	 	  if( mi[i].v>num )
 	 	  	  break;
 	 mi[i].v=num;
 	 mi[i].id=y;
 	 for( i=hema;ma[i].v!=INF;i++ )
 	 	  if( ma[i].v<num )
 	 	  	  break;
 	 ma[i].v=num;
 	 ma[i].id=y;
}

void insert0( int num,int y )
{
 	 while( y-mi[hemi].id>=c&&mi[hemi].v!=INF ) hemi++;
 	 if( num==INF ) return;
	 int a=0;
	 for( a=hemi;mi[a].v!=INF;a++ )
  	 	  if( mi[a].v>num )
 	  	  	  break;
	 mi[a].v=num;
	 mi[a].id=y; 	 	 					  	 
}

void insert1( int num,int y )
{
 	 while( y-ma[hema].id>=c&&mi[hema].v!=INF ) hema++;
 	 if( num==INF ) return;
 	 int a=0;
 	 for( a=hema;ma[a].v!=INF;a++ )
 	 	  if( ma[a].v<num )
 	 	  	  break;
 	 ma[a].v=num;
 	 ma[a].id=y;
}
int main()
{
 	while( scanf("%d%d%d%d",&n,&m,&r,&c)!=EOF )
 	{
	 	   for( int i=1;i<=n;i++ )
		   for( int j=1;j<=m;j++ )
	 	   	   	scanf( "%d",&mat[i][j] );
	 	   	   	
	 	   for( int j=1;j<=m;j++ )
	 	   {
		   		memset(mi,0x7F,sizeof(mi));
		   		memset(ma,0x7F,sizeof(ma));
		   		hemi=hema=0;
		   		for( int i=1;i<=n;i++ )
		   		{
		 	 	 	 insert(mat[i][j],i);
				 	 if( i>=r )
				 	 {
					  	 A[i-r+1][j]=mi[hemi].v;
					  	 B[i-r+1][j]=ma[hema].v;
				   	 }
	 	 	 	}
		   }
		   int ans=0;
		   for( int i=1;i-r+1<n;i++ )
		   {
		   		memset(mi,0x7F,sizeof(mi));
		   		memset(ma,0x7F,sizeof(ma));
		   		hema=hemi=0;
		   		for( int j=1;j-c+1<m;j++ )
		   		{
			  	 	 insert0( A[i][j],j );
			  	 	 insert1( B[i][j],j );
					 if( j>=c )
					 {
					  	 Mi[i][j-c+1]=mi[hemi].v;
					  	 Ma[i][j-c+1]=ma[hema].v;
					  	 ans=max( ans,Ma[i][j-c+1]-Mi[i][j-c+1] );
		  	 		 }
 	 	 		}
		   }
		   printf( "%d\n",ans );
  	}
 	return 0;
}