本文移植自个人的原博客（原文）

题目链接

Luogu 2216

题目描述

题目描述

题解

二维滑动窗口，先对每一行建立双端队列，记录每一个$1*n$的长方体中的极值，将二维矩阵压缩成$a$行$b-n+1$列的矩阵，再对每一列依次建立双端队列，记录$n*1$的长方体(在原矩阵中为$n*n$的正方形)中的极值（$miny[i][t],maxy[i][t]$存储的是以$(i,t)$为右下角端点的$n*n$正方形的极值信息），枚举即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int inf = 0x7fffffff;
const int N =1e3+1;
inline int get(int &x)
{
    x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
}
int x1[N],x2[N],headx1[N],tailx1[N],headx2[N],tailx2[N],minx[N][N],maxx[N][N];
int y1[N],y2[N],heady1[N],taily1[N],heady2[N],taily2[N],miny[N][N],maxy[N][N];
int mapp[N][N],a,b,n;
long long ans=inf;
int main()
{

    get(a),get(b),get(n);
    for(int i=1;i<=a;++i)for(int t=1;t<=b;++t)get(mapp[i][t]);
    for(int i=1;i<N;++i)headx1[i]=headx2[i]=heady1[i]=heady2[i]=1;
    for(int i=1;i<=a;++i)
    for(int t=1;t<=b;++t)
    {
        while(headx1[i]<=tailx1[i]&&mapp[i][x1[tailx1[i]]]>=mapp[i][t])tailx1[i]--;
        x1[++tailx1[i]]=t;
        while(headx1[i]<=tailx1[i]&&x1[headx1[i]]<=t-n)headx1[i]++;
        minx[i][t]=mapp[i][x1[headx1[i]]];
    }
    for(int i=1;i<=a;++i)
    for(int t=1;t<=b;++t)
    {
        while(headx2[i]<=tailx2[i]&&mapp[i][x2[tailx2[i]]]<=mapp[i][t])tailx2[i]--;
        x2[++tailx2[i]]=t;
        while(headx2[i]<=tailx2[i]&&x2[headx2[i]]<=t-n)headx2[i]++;
        maxx[i][t]=mapp[i][x2[headx2[i]]];
    }
    for(int t=n;t<=b;++t)
    for(int i=1;i<=a;++i)
    {
        while(heady1[t]<=taily1[t]&&minx[y1[taily1[t]]][t]>=minx[i][t])taily1[t]--;
        y1[++taily1[t]]=i;
        while(heady1[t]<=taily1[t]&&y1[heady1[t]]<=i-n)heady1[t]++;
        miny[i][t]=minx[y1[heady1[t]]][t];
    }
    for(int t=n;t<=b;++t)
    for(int i=1;i<=a;++i)
    {
        while(heady2[t]<=taily2[t]&&maxx[y2[taily2[t]]][t]<=maxx[i][t])taily2[t]--;
        y2[++taily2[t]]=i;
        while(heady2[t]<=taily2[t]&&y2[heady2[t]]<=i-n)heady2[t]++;
        maxy[i][t]=maxx[y2[heady2[t]]][t];
    }
    for(int t=n;t<=b;++t)
    for(int i=n;i<=a;++i)
    if(maxy[i][t]-miny[i][t]<ans)ans=maxy[i][t]-miny[i][t];
    printf("%lld",ans);
}