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

先想了一个比较暴力的想法，每一行维护一个st表，枚举左上角，查n行，复杂度O(n^3)，但是感觉比较松，因为n增大，查询的点也少，就试了试，有40分。

然后把高维数组压成一维，有60分。

然后加读入优化，O2可过 。

// luogu-judger-enable-o2
#include<iostream>
#include<cmath>
#include<cstdio>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
using namespace std;

struct file_io {
#define isdigit(ch) ((ch) >= '0' && (ch) <= '9')
    char inbuf[1 << 25], *pin, outbuf[1 << 25], *pout;
    int stk[20];

    file_io(): pout(outbuf) {
        fread(pin = inbuf, 1, 1 << 25, stdin);
    }
    ~file_io() {
        fwrite(outbuf, 1, pout - outbuf, stdout);
    }

    inline void getint(int &num) {
        bool neg = 0;
        num = 0;
        while(!isdigit(*pin)) if(*pin++ == '-') neg = 1;
        while(isdigit(*pin)) num = num * 10 + *pin++ - '0';
        if(neg) num = -num;
    }

    inline void putint(int num) {
        static int *v = stk;
        if(!num) *pout++ = '0';
        else {
            if(num < 0) *pout++ = '-', num = -num;
            for(; num; num /= 10) *v++ = num % 10;
            while(v != stk) *pout++ = *--v + '0';
        }
    }

    inline void nextline() {
        *pout++ = '
';
    }
} fio;
#define getint(num) fio.getint(num)
#define putint(num) fio.putint(num)
#define nextline() fio.nextline()

const int MAXN=1005;

const int t=10;
const int tt=10*MAXN;

int f[MAXN*tt+10];
int g[MAXN*tt+10];
int n,m,K;

int main() {
    getint(n);
    getint(m);
    getint(K);
    K--;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            int x=i*tt+j*t;
            getint(f[x]);
            g[x]=f[x];
        }
        for(int j=1; (1<<j)<=m; j++) {
            for(int k=1; k<=m; k++) {
                int x=i*tt+k*t+j,y=i*tt+(k+(1<<(j-1)))*t+j-1;
                f[x]=max(f[x-1],f[y]);
                g[x]=min(g[x-1],g[y]);
            }
        }
    }

    int ans=1<<30;
    int len=log2(K+1);
    for(int i=1; i+K<=n; i++) {
        for(int j=1; j+K<=m; j++) {
            int mx=-1,mn=1<<30;
            for(int k=i; k<=i+K; k++) {
                int x=k*tt+j*t+len,y=k*tt+(j+K-(1<<len)+1)*t+len;
                mx=max(mx,max(f[x],f[y]));
                mn=min(mn,min(g[x],g[y]));
            }
            ans=min(ans,mx-mn);
        }
    }
    putint(ans);
    return 0;
}