p2216理想正方形求优化思路

运行时长14s......全TLE了。。。

用的单调队列思路，不知道为啥没输出。。 先求行的最大最小，然后求新矩阵里的列最大最小， 最终得到最大和最小，后做差。

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e3+10;
int a=0,b=0;
int m[maxn][maxn],q[maxn];
int lmax[maxn][maxn],lmin[maxn][maxn];
int hmax[maxn][maxn],hmin[maxn][maxn];
long long ans=1e9,n=0;
void read(){
    cin>>a>>b>>n;
    for(int i=1;i<=a;++i){
        for(int j=1;i<=b;++j){
            cin>>m[i][j];
        }
    }
    for(int row=1;row<=a;row++){
        int h=0,t=0;
        for(int i=1;i<=b;++i){
            while(h<t && q[h]+n<=i) h++;
            while(h<t && m[row][q[t-1]]<m[row][i]) t--;
            q[t]=i;
            t++;
            if(i>=n) hmax[row][i-n+1]=m[row][q[h]];
        }
        h=0,t=0;
        for(int i=1;i<=b;++i){
            while(h<t && q[h]+n<=i) h++;
            while(h<t && m[row][q[t-1]]>m[row][i]) t--;
            q[t]=i;
            t++;
            if(i>=n) hmin[row][i-n+1]=m[row][q[h]];
        }
    }   
    for(int l=1;l<=b-n+1;++l){
        int h=0,t=0;
        for(int i=1;i<=a;++i){
            while(h<t && q[h]+n<=i) h++;
            while(h<t && hmax[q[t-1]][l]<hmax[i][l]) t--;
            q[t]=i;
            t++;
            if(i>=n) lmax[i-n+1][l]=hmax[q[h]][l];
        }
        h=0,t=0;
        for(int i=1;i<=a;++i){
            while(h<t && q[h]+n<=i) h++;
            while(h<t && hmin[q[t-1]][l]>hmin[i][l]) t--;
            q[t]=i;
            t++;
            if(i>=n) lmin[i-n+1][l]=hmin[q[h]][l];
        }
    }
    for(int i=1;i<=a-n+1;++i){
        for(int j=1;j<=b-n+1;++j){
            if(lmax[i][j]-lmin[i][j]<ans){
                ans=lmax[i][j]-lmin[i][j];
            }
        }
    }
    cout<<ans;
}