理想正方形

题目地址

二维的单调队列题。
错因：统计答案时必须(i>=n)并且(j>=n)才能更新答案，这里没判断。而如果(i\,,j)都从(n)开始枚举的话，列的话是没问题的（因为(ans)数组里存的是这一个点向前最多(n)个位置的最大值或最小值），但是考虑行，前(n)行的值都会被忽略，也就是说答案只会从第(n)行开始统计答案。
最终(AC)代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1005;
int n,a,b,l=1,r,l1=1,r1,v[N][N],ansd[N][N],ansx[N][N];
int ans=2147483647,tmp1[N][N],tmp2[N][N];
struct node{
	int id,val;
}q[N],q1[N];
int main()
{
	scanf("%d%d%d",&a,&b,&n);
	for(int i=1;i<=a;i++)
	 for(int j=1;j<=b;j++)
	  scanf("%d",&v[i][j]);
	for(int t=1;t<=a;t++)
	{
		l=1,r=0; l1=1,r1=0;
	    for(int i=1;i<=b;i++)
	    {
	    	while(l<=r&&i-q[l].id>=n) ++l;
	    	while(l1<=r1&&i-q1[l1].id>=n) ++l1;
	    	while(q[r].val<=v[t][i]&&l<=r) --r;//r --> l<=r 
	    	while(q1[r1].val>=v[t][i]&&l1<=r1) --r1;//
	    	q[++r].id=i; q[r].val=v[t][i];
	    	q1[++r1].id=i; q1[r1].val=v[t][i];
//	    	if(t==2&&i==4) cout<<l1<<"**********"<<r1<<endl;
	    	ansd[t][i]=q[l].val,ansx[t][i]=q1[l1].val;
	    }
	}
/*	for(int i=1;i<=a;i++)
	{ 
	 for(int j=1;j<=b;j++)
	 	printf("%d*",ansd[i][j]);
	cout<<endl;
	}*/
	for(int i=1;i<=b;i++)
	{
		l=1,r=0; l1=1,r1=0;
		for(int j=1;j<=a;j++)
		{
			while(l<=r&&j-q[l].id>=n) ++l;
			while(l1<=r1&&j-q1[l1].id>=n) ++l1;
			while(l<=r&&q[r].val<=ansd[j][i]) --r;
			while(l1<=r1&&q1[r1].val>=ansx[j][i]) --r1;
			q[++r].id=j; q[r].val=ansd[j][i];
			q1[++r1].id=j; q1[r1].val=ansx[j][i];
			tmp1[j][i]=q[l].val; tmp2[j][i]=q1[l1].val;
			if(i>=n&&j>=n) ans=min(ans,q[l].val-q1[l1].val);
		}
	}
//	for(int i=n;i<=a;i++)
//	 for(int j=n;j<=b;j++)
//	  ans=min(ans,tmp1[i][j]-tmp2[i][j]);
	printf("%d
",ans);
	return 0;
}
/*
6 6 3
3 5 4 7 8 9 
12 4 5 8 12 36
14 25 3 6 22 1
25 36 11 44 21 2
2 5 89 4 5 7
3 6 5 4 8 2 
*/