BZOJ1047 [HAOI2007]理想的正方形（洛谷P2216）

單調隊列

BZOJ題目傳送門

洛谷題目傳送門

先對原矩陣預處理出每一行的最大和最小值，對處理出來的這個數組再處理一遍最大最小值， n2 n 2 枚舉就好了。處理用單調隊列。

代碼：

#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 1005
using namespace std;
int n,m,k,ans,a[N][N],q[N],X[N][N],Y[][N][N];
inline char readc(){
    static char buf[],*l=buf,*r=buf;
    if (l==r) r=(l=buf)+fread(buf,,,stdin);
    if (l==r) return EOF; return *l++;
}
inline int _read(){
    int x=; char ch=readc();
    while (!isdigit(ch)) ch=readc();
    while (isdigit(ch)) x=(x<<)+(x<<)+(ch^),ch=readc();
    return x;
}
inline void doit(bool f){
    for (int i=;i<=n;i++)
        for (int j=,l=,r=;j<=m;j++){
            while (l<=r&&q[l]<=j-k) l++;
            if (f) while (l<=r&&a[i][j]>=a[i][q[r]]) r--;
            else while (l<=r&&a[i][j]<=a[i][q[r]]) r--;
            q[++r]=j,X[i][j]=a[i][q[l]];
        }
    memset(q,,sizeof(q));
    for (int j=k;j<=m;j++)
        for (int i=,l=,r=;i<=n;i++){
            while (l<=r&&q[l]<=i-k) l++;
            if (f) while (l<=r&&X[i][j]>=X[q[r]][j]) r--;
            else while (l<=r&&X[i][j]<=X[q[r]][j]) r--;
            q[++r]=i,Y[f][i][j]=X[q[l]][j];
        }
}
int main(){
    n=_read(),m=_read(),k=_read();
    for (int i=;i<=n;i++)
        for (int j=;j<=m;j++)
            a[i][j]=_read();
    doit(),doit(),ans=e9;
    for (int i=k;i<=n;i++)
        for (int j=k;j<=m;j++)
            ans=min(ans,Y[][i][j]-Y[][i][j]);
    return printf("%d\n",ans),;
}