#include#include #include using namespace std;int a,b,n;int m[1005][1005],q[7][1005][2005];int head[7][1005],tail[7][1005],l[5][1005],r[3][1005];int main(){ while(~scanf("%d%d%d",&a,&b,&n)){ int i,j,k; for(i=1;i<=a;++i){ for(j=1;j<=b;++j){ scanf("%d",&m[i][j]); } } for(i=1;i<=b;++i) { l[2][i]=r[2][i]=1; } memset(head,0,sizeof(head)); memset(tail,0,sizeof(tail)); int ans=~(0u)>>1; for(i=1;i<=a-n+1;++i){ int row=i; l[1][i]=r[1][i]=1; while(r[1][i]<=b){ while(r[1][i]-l[1][i]+1<=n){ int col=r[1][i]; while(r[2][col]-l[2][col]+1<=n){ int t=r[2][col]; while(head[3][col]!=tail[3][col]&&m[q[3][col][tail[3][col]-1]][col]<=m[t][col]) tail[3][col]--; q[3][col][tail[3][col]++]=t; while(head[4][col]!=tail[4][col]&&m[q[4][col][tail[4][col]-1]][col]>=m[t][col]) tail[4][col]--; q[4][col][tail[4][col]++]=t; r[2][col]++; } while(head[1][row]!=tail[1][row]&&head[5][row]!=tail[5][row]&&m[q[5][row][tail[5][row]-1]][q[1][row][tail[1][row]-1]]<=m[q[3][col][head[3][col]]][col]) { tail[1][row]--,tail[5][row]--; } q[1][row][tail[1][row]++]=col,q[5][row][tail[5][row]++]=q[3][col][head[3][col]]; while(head[2][row]!=tail[2][row]&&head[6][row]!=tail[6][row]&&m[q[6][row][tail[6][row]-1]][q[2][row][tail[2][row]-1]]>=m[q[4][col][head[4][col]]][col]) { tail[2][row]--,tail[6][row]--; } q[2][row][tail[2][row]++]=col,q[6][row][tail[6][row]++]=q[4][col][head[4][col]]; l[2][col]++; while(head[3][col]!=tail[3][col]&&q[3][col][head[3][col]]
竖着跑一遍单调队列，跑完竖的所有列，再对所有列的最值跑一遍行的