bzoj1047 [haoi2007]理想的正方形

using namespace std;
const int maxn=1000+5;
int a,b,n;
int num[maxn][maxn];
int maxi[maxn][maxn],mini[maxn][maxn];
int maxc[maxn][maxn],minc[maxn][maxn];
struct {
    priority_queue<int > a,b;
    void ini(){while(!a.empty()) a.pop();while(!b.empty()) b.pop();}
    void add(int x) {a.push(x);}
    void del(int x) {b.push(x);}
    int getmax(){
        while(!b.empty() && a.top()==b.top()) {a.pop();b.pop();}
        return a.top();
    }
};
struct pq_Min{
    priority_queue<int ,vector<int> ,greater<int > > a,b;
    void ini(){while(!a.empty()) a.pop();while(!b.empty()) b.pop();}
    void add(int x) {a.push(x);}
    void del(int x) {b.push(x);}
    int getmin(){
        while(!b.empty() && a.top()==b.top()) {a.pop();b.pop();}
        return a.top();
    }
};
int main()
{
    scanf("%d%d%d",&a,&b,&n);
    for(int i=1;i<=a;i++)
        for(int j=1;j<=b;j++)scanf("%d",&num[i][j]);
    for(int i=1;i<=a;i++)
    {
        pq_Max bq;pq_Min sq;bq.ini();sq.ini();
        for(int j=1;j<=b;j++)
        {
            bq.add(num[i][j]);sq.add(num[i][j]);
            if(j>=n){
                maxi[i][j]=bq.getmax();mini[i][j]=sq.getmin();
                bq.del(num[i][j-n+1]);sq.del(num[i][j-n+1]);
            }
        }
    }
    for(int j=n;j<=b;j++)
    {
        pq_Max bq;pq_Min sq;
        bq.ini();sq.ini();
        for(int i=1;i<=a;i++)
        {
            bq.add(maxi[i][j]);sq.add(mini[i][j]);
            if(i>=n){
                maxc[i][j]=bq.getmax();minc[i][j]=sq.getmin();
                bq.del(maxi[i-n+1][j]);sq.del(mini[i-n+1][j]);
            }
        }
    }
    int res=0x3f3f3f3f;
    for(int i=n;i<=a;i++)
        for(int j=n;j<=b;j++)
            res=min(res,maxc[i][j]-minc[i][j]);
    printf("%dn",res);
    return 0;
}