P2216 理想的正方形 单调队列 （二维）

题目链接：https://www.luogu.org/problem/P2216

题意：求给定n*m的矩形中所有k*k的正方形块中最大值最小值之差（极差）最小

哇，大神的思路真的很帅

单调队列对每一行求一个k项最大最小

用X[i][j]表示第i行小于j-k+1~j的最大值

用X[i][j]表示第i行小于j-k+1~j的最大值

然后处理完行之后，用X，x数组作为基础对每一列求最大最小,用Y,y表示

这样处理完的Y[i][j]就表示以i，j为右下角的k*k矩形的最大值

这样处理完的y[i][j]就表示以i，j为右下角的k*k矩形的最小值

给他起个名字就叫二位单调队列吧QAQ~

此图是偷的~

代码如下啦：

//#pragma comment (linker, "/STACK:102400000,102400000")
#include<bits/stdc++.h>
#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#include<list>
#include<time.h>
#include<bitset>

#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define lowbit(x) x&(-x)
#define min4(a, b, c, d) min(min(a,b),min(c,d))
#define min3(x, y, z) min(min(x,y),z)
#define max3(x, y, z) max(max(x,y),z)
#define max4(a, b, c, d) max(max(a,b),max(c,d))
#define pii make_pair
#define pr pair<int,int>
typedef unsigned long long ull;
typedef long long ll;
const int inff = 0x3f3f3f3f;
const long long inFF = 9223372036854775807;
const int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
const int mdir[8][2] = {0, 1, 0, -1, 1, 0, -1, 0, 1, 1, -1, 1, 1, -1, -1, -1};
const double eps = 1e-10;
const double PI = acos(-1.0);
const double E = 2.718281828459;
using namespace std;
const int mod=1e9+7;
const int maxn=1005;
int a[maxn][maxn];
int X[maxn][maxn],x[maxn][maxn],Y[maxn][maxn],y[maxn][maxn];
int Q[maxn],q[maxn];
int main()
{
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
    for(int i=1;i<=n;i++)
    {
        int l=0,r=0,L=0,R=0;
        Q[0]=0,q[0]=0;
        for(int j=1;j<=m;j++)
        {
            while(l<=r&&a[i][j-1]<=a[i][q[r]]) r--;
            while(L<=R&&a[i][j-1]>=a[i][Q[R]]) R--;
            q[++r]=j-1,Q[++R]=j-1;
            while(l<=r&&q[l]<=j-k) l++;
            while(L<=R&&Q[L]<=j-k) L++;
            x[i][j]=min(a[i][q[l]],a[i][j]);
            X[i][j]=max(a[i][Q[L]],a[i][j]);
        }
    }
    for(int i=k;i<=m;i++)
    {
        int l=0,r=0,L=0,R=0;
        Q[0]=0,q[0]=0;
        for(int j=1;j<=n;j++)
        {
            while(l<=r&&x[j-1][i]<=x[q[r]][i]) r--;
            while(L<=R&&X[j-1][i]>=X[Q[R]][i]) R--;
            q[++r]=j-1,Q[++R]=j-1;
            while(l<=r&&q[l]<=j-k) l++;
            while(L<=R&&Q[L]<=j-k) L++;
            y[j][i]=min(x[j][i],x[q[l]][i]);
            Y[j][i]=max(X[j][i],X[Q[L]][i]);
        }
    }
    int ans=inff;
    for(int i=k;i<=n;i++)
        for(int j=k;j<=m;j++)
            ans=min(ans,Y[i][j]-y[i][j]);
    cout<<ans<<endl;
}