Luogu

BZOJ

分析

直接上二维$\texttt{ST}$表。

预处理是$O(n^2\,\log^2\,n)$的，枚举+查询是$O(n^2)$的。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int max(int a,int b,int c,int d) { return max(max(a,b),max(c,d)); }
inline int min(int a,int b,int c,int d) { return min(min(a,b),min(c,d)); }    
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int INF=2147483647;
const int N=1000+10;

int n,m,k,t;
int a[N][N];
int f[N][N][11],g[N][N][11];

inline void build() {
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=m;++j)
            f[i][j][0]=g[i][j][0]=a[i][j];
    for (re int k=0;k<10;++k)
        for (re int i=1;i<=n-(1<<k);++i)
            for (re int j=1;j<=m-(1<<k);++j) {
                f[i][j][k+1]=max(f[i][j][k],
                                 f[i+(1<<k)][j][k],
                                 f[i][j+(1<<k)][k],
                                 f[i+(1<<k)][j+(1<<k)][k]);
                g[i][j][k+1]=min(g[i][j][k],
                                 g[i+(1<<k)][j][k],
                                 g[i][j+(1<<k)][k],
                                 g[i+(1<<k)][j+(1<<k)][k]);
            }
}

inline int query(int x,int y) {
    int mx=max(f[x][y][t],
               f[x+k-(1<<t)][y][t],
               f[x][y+k-(1<<t)][t],
               f[x+k-(1<<t)][y+k-(1<<t)][t]);
    int mn=min(g[x][y][t],
               g[x+k-(1<<t)][y][t],
               g[x][y+k-(1<<t)][t],
               g[x+k-(1<<t)][y+k-(1<<t)][t]);
    return mx-mn;
}

int main() {
    n=read(),m=read(),k=read(),t=log(k)/log(2);
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=m;++j)
            a[i][j]=read();
    build();
    int ans=INF;
    for (re int i=1;i<=n-k+1;++i)
        for (re int j=1;j<=m-k+1;++j)
            ans=min(ans,query(i,j));
    printf("%d\n",ans);
    return 0;
}