[HAOI]2007理想の正方形

[HAOI]2007理想の正方形
本題の住所:http://www.luogu.org/problem/show?pid=2216
タイトルの説明
a*bの整数からなるマトリクスがあります.ここで、n*nの正方形領域を見つけて、その領域のすべての数の最大値と最小値の差を最小にしてください.
にゅうしゅつりょくけいしき
入力フォーマット:第1の動作の3つの整数は、それぞれa,b,nの値を表し、第2の行から第a+1の行まで、動作bごとに非負の整数を表し、マトリクス内の対応する位置の数を表す.行ごとに隣接する2つの数の間にスペースで区切られます.
出力フォーマット:a*bマトリクス内のすべての「n*n正方形領域における最大整数と最小整数の差」の最小値である整数のみ.
入出力サンプル入力サンプル#1:5 4 2 1 2 5 6 0 17 16 0 17 2 1 2 2 10 2 1 2 2 2出力サンプル#1:1————-(著者注:明らかに右下角あれ=)問題規模(1)マトリクス中のすべての数が10000000(2)20%を超えないデータ2<=a,b<=100,n<=a,n<=b,n<=10(3)100%のデータ2<=a,b<=1000,n<=a,n<=b,n<=100
問題解
この問題を手に入れたのはメンテナンス区間の最大最小値のようですか?二次元の線分樹かな=(書けないけど)->O(a*b*n^2)暴力しかできないけど、20もないみたい(あるらしい...でも卵がない=)神たちの題解を見に行こう->しかし単調な行列は何なのか、これまで書いたことがないようです.->元の行列をb列に分けてスライドウィンドウを1回ずつ行う単調キューウィンドウ長はnですか->そして配列を開いてメモします.例えばMax[i][j]はi行目j-n+1列目からj列目までの最大値を表す->このときn行が1行に圧縮され(最大値のみが要求されるのか)Max[i][j]を利用します.さらに単調なキューを出すとn点ごとに1つの点開配列に押されて記録される.例えばMAX[i][j]はi,jを右下角とするn*nの矩形の最大値を表す->最小値も上記のようにすればいい.そして暴力(a-n)*(b-n)は最小差を探す->は実は4回の単調なキュー==このような神題は見たことがない(DPを無理に計算しようか?)
コード#コード#
(入力データは百万あります)(4回の単調なキューはほとんど差がなく、コピーすればいいのですが、ウィンドウを縦に滑るときに2次元ではなく1次元になることに注意します)(dequeを使いたくないので手書きでキューを書いて2つのキューを一緒に書くのが卵が痛いと感じて4つの関数==を書きました)

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1000+10;
const int INF=(1<<30);

int a,b,n,map[maxn][maxn];
int Max[maxn][maxn],Min[maxn][maxn];
int MAX[maxn][maxn],MIN[maxn][maxn];

int read()
{
    int ret=0;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    for(;ch>='0'&&ch<='9';ch=getchar()) ret=ret*10+ch-'0';
    return ret;
}

void init_data()
{
    cin>>a>>b>>n;
    for(int i=1;i<=a;i++)
       for(int j=1;j<=b;j++)
          map[i][j]=read();
}

void cal0(int x)// cal max downer          
{
    int win[maxn]={0},rear,front;
    win[1]=1;
    rear=front=1;
    for(int i=2;i<=a;i++)
    {
        if(win[rear]<=i-n) rear++;
        if(front==0) win[++front]=i;
        else
        {
            while(front>0&&(map[i][x]>map[win[front]][x]&&front>=rear)) front--;
            win[++front]=i;
        }
        if(i>=n) Max[i][x]=map[win[rear]][x];
    }
}

void cal1(int x)// cal min upper        
{
    int win[maxn]={0},rear,front;
    win[1]=1;
    rear=front=1;
    for(int i=2;i<=a;i++)
    {
        if(win[rear]<=i-n) rear++;
        if(front==0) win[++front]=i;
        else
        {
            while(front>0&&(map[i][x]<map[win[front]][x]&&front>=rear)) front--;
            win[++front]=i;
        }
        if(i>=n) Min[i][x]=map[win[rear]][x];
    }
}

void cal2(int x)//        Max    MAX
{
    int *m=Max[x];
    int win[maxn]={0},rear,front;
    win[1]=1;
    rear=front=1;
    for(int i=2;i<=b;i++)
    {
        if(win[rear]<=i-n) rear++;
        if(front==0) win[++front]=i;
        else
        {
            while(front>0&&(m[i]>m[win[front]]&&front>=rear)) front--;
            win[++front]=i;
        }
        if(i>=n) MAX[x][i]=m[win[rear]];
    }
}

void cal3(int x)//  
{
    int *m=Min[x];
    int win[maxn]={0},rear,front;
    win[1]=1;
    rear=front=1;
    for(int i=2;i<=b;i++)
    {
        if(win[rear]<=i-n) rear++;
        if(front==0) win[++front]=i;
        else
        {
            while(front>0&&(m[i]<m[win[front]]&&front>=rear)) front--;
            win[++front]=i;
        }
        if(i>=n) MIN[x][i]=m[win[rear]];
    }
}

int main()
{
    init_data();
    for(int i=1;i<=b;i++) cal0(i);
    for(int i=1;i<=b;i++) cal1(i);
    for(int i=n;i<=a;i++) cal2(i);
    for(int i=n;i<=a;i++) cal3(i);
    int ans=INF;
    for(int i=n;i<=a;i++) 
       for(int j=n;j<=b;j++)
          ans=min(ans,MAX[i][j]-MIN[i][j]);
    printf("%d",ans);
    return 0;
} 

DP神題%%