BZOJ-1047: [HAOI2007]理想的正方形

Description

有一个a*b的整数组成的矩阵，现请你从中找出一个n*n的正方形区域，使得该区域所有数中的最大值和最小值的差最小。2<=a,b<=1000,n<=a,n<=b,n<=1000

据大师说二维RMQ会被卡。所以那就上单调队列吧。
然后发现单调队列的移动是O(n)的。整个是O()。然后优化。对于一整列，只需要扔进去这一列最大和最小的就好了。所以预处理一下每一列长度为n的最大最小值就好了。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int a,b,n,map[1100][1100],mx[1100][1100],mi[1100][1100];
int ans=1<<30;
inline int read()
{
    char ch=getchar();int re=0;
    while(ch<'0'|ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9')
        re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
    return re;
}

void initialize()
{
    static int mxq[1100],miq[1100];
    for(int i=1;i<=b;i++)
    {
        int mxl=1,mxr=0,mil=1,mir=0;
        for(int j=1;j<=a;j++)
        {
            while(mxl<=mxr&&map[mxq[mxr]][i]<=map[j][i]) mxr--;
            mxq[++mxr]=j;
            while(mil<=mir&&map[miq[mir]][i]>=map[j][i]) mir--;
            miq[++mir]=j;
            if(j-mxq[mxl]==n) mxl++;
            if(j-miq[mil]==n) mil++;
            mx[j][i]=map[mxq[mxl]][i],mi[j][i]=map[miq[mil]][i];
        }
    }
}
int main()
{
    a=read(); b=read(); n=read();
    for(int i=1;i<=a;i++)
        for(int j=1;j<=b;j++)
            map[i][j]=read();
    initialize();
    for(int i=n;i<=a;i++)
    {
        static int mxq[1100],miq[1100];
        int mxl=1,mxr=0,mil=1,mir=0;
        for(int j=1;j<=b;j++)
        {
            while(mxl<=mxr&&mx[i][mxq[mxr]]<=mx[i][j]) mxr--;
            mxq[++mxr]=j;
            while(mil<=mir&&mi[i][miq[mir]]>=mi[i][j]) mir--;
            miq[++mir]=j;
            if(j-mxq[mxl]==n) mxl++;
            if(j-miq[mil]==n) mil++;
            if(j>=n) ans=min(ans,mx[i][mxq[mxl]]-mi[i][miq[mil]]);
        }
    }
    printf("%d\n",ans);
    return 0;
}