题目
单调队列是个很神奇的东西，我以前在博客写过（吧）
我很佩服rank里那些排前几的大神，700ms做了时限10s的题，简直不能忍。（但是我还是不会写
我大概一年半没写单调队列，也有可能根本没有写过
放两个程序，第一个TLE，第二个3s+直接通过
哦对了！单调队列的复杂度为O(n)，很经典的证明呢
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXab=1000+7,MAXn=100+7,inf=2147483647;
typedef int MATRIX[MAXn][MAXab][MAXab];
MATRIX fmin,fmax;
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a>b?b:a;}
inline int min4(int a,int b,int c,int d){return min(min(min(a,b),c),d);}
inline int max4(int a,int b,int c,int d){return max(max(max(a,b),c),d);}
int main(){
//freopen("b1047.in","r",stdin);
int a,b,n;
scanf("%d%d%d",&a,&b,&n);
for (int i=1;i<=a;i++)
for (int j=1;j<=b;j++) {
scanf("%d",&fmin[1][i][j]);
fmax[1][i][j]=fmin[1][i][j];
}
int ans=inf;
for (int k=2;k<=n;k++){ //kは决策です！
for (int i=1;i<=a-k+1;i++)
for (int j=1;j<=b-k+1;j++){
fmin[k][i][j]=
min4(fmin[k-1][i][j],fmin[k-1][i+1][j],
fmin[k-1][i][j+1],fmin[k-1][i+1][j+1]);
fmax[k][i][j]=
max4(fmax[k-1][i][j],fmax[k-1][i+1][j],
fmax[k-1][i][j+1],fmax[k-1][i+1][j+1]);
if (k==n) ans=min(fmax[k][i][j]-fmin[k][i][j],ans);
}
}
printf("%d",ans);
return 0;
}
/*优先队列！*/
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXn=100+7,MAXab=1000+7;
const int inf=0x7fffffff;
int n,a,b,fmin[MAXab][MAXab],fmax[MAXab][MAXab];
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
int main(){
// freopen("b1047.in","r",stdin);
// freopen("b1047.out","w",stdout);
scanf("%d%d%d",&a,&b,&n);
for (int i=1;i<=a;i++){
int ts,ws,tb,wb,qs[MAXab]={0},qb[MAXab]={-inf},v[MAXab]={0};
ts=ws=tb=wb=1;
for (int j=1;j<=b;j++){
scanf("%d",&v[j]);
while (ws-->ts&&v[j]<v[qs[ws]]);ws++;qs[ws++]=j;
if (qs[ws-1]-qs[ts]+1>n) ts++;
while (wb-->tb&&v[j]>v[qb[wb]]);wb++;qb[wb++]=j;
if (qb[wb-1]-qb[tb]+1>n) tb++;
if (j>=n) fmin[i][j-n+1]=v[qs[ts]],fmax[i][j-n+1]=v[qb[tb]];
}
}
int ans=inf;
for (int i=1;i<=a-n+1;i++){
for (int j=1;j<=b-n+1;j++){
int minans=inf,maxans=-inf;
for (int k=0;k<n;k++){
minans=min(minans,fmin[i+k][j]);
maxans=max(maxans,fmax[i+k][j]);
}
ans=min(ans,maxans-minans);
}
}
cout<<ans<<endl;
return 0;
}