记录编号	192777	评测结果	AAAAAAAAAA
题目名称	[HAOI 2007]理想的正方形	最终得分	100
用户昵称	炽烈的爱	是否通过	通过
代码语言	C++	运行时间	1.608 s
提交时间	2015-10-12 21:01:44	内存使用	38.01 MiB

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#define N 1111
#define BUG system("pause")
using namespace std;
long long a,b,n;
long long map[N][N];
long long q[N][N],h[N],t[N],s,e,dq[N];
long long mx[N][N],ans,mn[N][N];
inline void read()
{
    scanf("%lld%d%d",&a,&b,&n);
    for(long long i=1;i<=a;i++)
        for(long long j=1;j<=b;j++)
            scanf("%lld",&map[i][j]);
}
inline void getmax()
{
    for(long long i=1;i<=b;i++)
		h[i]=1,t[i]=0;
    for(long long i=1;i<=a;i++)
    {
        for(long long j=1;j<=b;j++)
        {

            while(h[j]<=t[j]&&i-q[j][h[j]]+1>n) h[j]++;
            while(h[j]<=t[j]&&map[q[j][t[j]]][j]<=map[i][j]) t[j]--;
            q[j][++t[j]]=i;
        }
        e=0; s=1;
        for(long long j=1;j<=b;j++)
        {
            while(s<=e&&j-dq[s]+1>n) s++;
            while(s<=e&&map[q[dq[e]][h[dq[e]]]][dq[e]]<=map[q[j][h[j]]][j]) e--;
            dq[++e]=j;
            mx[i][j]=map[q[dq[s]][h[dq[s]]]][dq[s]];
        }
    }
}

inline void getmin()
{
    for(long long i=1;i<=b;i++) h[i]=1,t[i]=0;
    for(long long i=1;i<=a;i++)
    {
        for(long long j=1;j<=b;j++)
        {
            while(h[j]<=t[j]&&i-q[j][h[j]]+1>n) h[j]++;
            /*删除的时候，判断队首，如果队首元素下标小于当前段左边界就删除，
			不断删除队首直到队首元素下标大于等于当前段左边界
			（注意：这时队列肯定不为空），队首元素就是当前段的最优解。*/
            while(h[j]<=t[j]&&map[q[j][t[j]]][j]>=map[i][j]) t[j]--;
            /*为了保证单调性，每次插入的时候，先判断队尾元素，
			如果不比待插入元素小就删除，
			不断删除队尾直到队尾元素小于待插入元素或者队空。*/
            q[j][++t[j]]=i;
        }
        e=0; s=1;
        for(long long j=1;j<=b;j++)
        {
            while(s<=e&&j-dq[s]+1>n) s++;
            while(s<=e&&map[q[dq[e]][h[dq[e]]]][dq[e]]>=map[q[j][h[j]]][j]) e--;
            /*初始的时候分别把当前行前n-1个元素插入队尾。从第1列开始，
			每次取队首最优值，从队首删除无效元素，并将当前列+n-1号元素插入队尾。*/
            dq[++e]=j;
            mn[i][j]=map[q[dq[s]][h[dq[s]]]][dq[s]];
        }
    }
}

inline void go()
{
    getmin();
    getmax();
    ans=1LL<<60;
    for(long long i=n;i<=a;i++)
        for(long long j=n;j<=b;j++)
            ans=min(ans,mx[i][j]-mn[i][j]);
    printf("%lld\n",ans);
}

int main()
{
	freopen("square.in","r",stdin);
	freopen("square.out","w",stdout);
    read(),go();
    return 0;
}