[HAOI2007] 理想的正方形 (单调队列)

题目链接

Solution

MD,经过这道题,算是掌握单调队列了...
可以先预处理出点 ((i,j)) 往上 (n) 的最大值和最小值.
然后再横着做一遍单调队列即可.

Code

#include<bits/stdc++.h>
#define in(x) x=read();
#define ll long long
#define N 1001
using namespace std;

ll read()
{
	char ch=getchar(); ll f=1,w=0;
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){w=w*10+ch-'0';ch=getchar();}
	return f*w;
}

ll Mx[N][N],Mn[N][N];
ll a,n,m,w[N][N];
ll ans=0x3f3f3f3f3f;

int main()
{
	in(n); in(m); in(a);
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	in(w[i][j]);
	
 	for(int j=1;j<=m;j++)
    {
        int head=1,tail=0,q[N];
        for(int i=1;i<=n;i++)
        {
            while(head<=tail&&w[q[tail]][j]>=w[i][j]) tail--;
            q[++tail]=i;
            while(q[tail]-q[head]>=a) head++;
            Mn[j][i]=w[q[head]][j];
        }
        head=1;tail=0;
        for(int i=1;i<=n;i++)
        {
            while(head<=tail&&w[q[tail]][j]<=w[i][j]) tail--;
            q[++tail]=i;
            while(q[tail]-q[head]>=a) head++;
            Mx[j][i]=w[q[head]][j];
        }
    }
    for(int i=a;i<=n;i++)
    {
        int h=1,t=0,H=1,T=0;
       	ll minn,maxx,q1[N],q2[N];
        for(int j=1;j<=m;j++)
        {
            while(h<=t&&Mn[q1[t]][i]>=Mn[j][i]) t--;
            while(H<=T&&Mx[q2[T]][i]<=Mx[j][i]) T--;
            q1[++t]=j;q2[++T]=j;
            while(q1[t]-q1[h]>=a) h++;
            while(q2[T]-q2[H]>=a) H++;
            minn=Mn[q1[h]][i];
            maxx=Mx[q2[H]][i];
            if(j>=a)
            ans=min(ans,maxx-minn);
        }
    }
    cout<<ans;
}