洛谷2216 [HAOI2007]理想的正方形

题意

给出一个 $A\times B$ 的矩阵，要求求出一个子矩阵，满足子矩阵中最大值和最小值的差值最大。

$A,B\le 1000$ 。

题解

先对每行用单调队列求出最大/最小值，记录在 $maxx[],minx[]$ 中。然后对这两个数组的每列用单调队列再求出最大/最小值，即可得到答案。

#include<bits/stdc++.h>

using namespace std;

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

const int N=1005;
deque <int> mx,mn;
int a,b,n,s[N][N],maxx[N][N],minx[N][N];

signed main()
{
    a=read(); b=read(); n=read();
    for (int i=1;i<=a;i++)
    {
        mx.clear(); mn.clear();
        for (int j=1;j<=b;j++)
        {
            s[i][j]=read();
            while (!mn.empty() && mn.front()<=j-n) mn.pop_front();
            while (!mx.empty() && mx.front()<=j-n) mx.pop_front();
            while (!mn.empty() && s[i][j]<=s[i][mn.back()]) mn.pop_back();
            while (!mx.empty() && s[i][j]>=s[i][mx.back()]) mx.pop_back();
            mn.emplace_back(j);
            mx.emplace_back(j);
            if (j>=n) maxx[i][j-n+1]=s[i][mx.front()],minx[i][j-n+1]=s[i][mn.front()];
        }
    }
    int maxj=b-n+1,ans=1e9;
    for (int j=1;j<=maxj;j++)
    {
        mx.clear(); mn.clear();
        for (int i=1;i<=a;i++)
        {
            while (!mn.empty() && mn.front()<=i-n) mn.pop_front();
            while (!mx.empty() && mx.front()<=i-n) mx.pop_front();
            while (!mn.empty() && minx[i][j]<=minx[mn.back()][j]) mn.pop_back();
            while (!mx.empty() && maxx[i][j]>=maxx[mx.back()][j]) mx.pop_back();
            mn.emplace_back(i);
            mx.emplace_back(i);
            if (i>=n) ans=min(ans,maxx[mx.front()][j]-minx[mn.front()][j]);
        }
    }
    return !printf("%d",ans);
}