题解：P2216 [HAOI2007] 理想的正方形

· · 题解

P2216 [HAOI2007] 理想的正方形 题解

猫猫切得最快的绿题，30 分钟就切了泪目。

注：本文中所有双引号都是为了断句，无特殊意义。

题意

给定 p_{1 \sim a , 1 \sim b}，求其中所有形状为“边长为 n 的正方形”的块内，最大值与最小值的差的最小值。

思路

注，下面是求 \max 的思路，求 \min 完全同理。

:::info[考虑暴力]{open}

首先，遍历每个点作为正方形右下角，再遍历正方形每个点求 \max，模拟即可，O(abn^2)。

:::

:::info[考虑优化]{open}

显然，块内的最大值是“每行中元素最大值”的最大值，所以可以预处理每个长度为 n，宽度为 1 的长条内的最大值。遍历整个图的行下标，在遍历列下标的时候用单调队列求出长条的最大值（不会的参见这里），预处理时间为 O(ab)。再求的时候遍历每个点作为正方形右下角，再遍历正方形的行下标，取每行预处理好的最大值做 \max 就好了，O(abn)。我不知道能不能过。

:::

:::info[继续优化]{open}

预处理之后的部分看起来很好优化的样子！那就再来一次预处理吧！

既然我们预处理好后还需遍历行下标求 \max，那我们为什么不把这一步也用单调队列处理了呢？求出来预处理数组 maxn 后，再求 maxn 数组中长度为 1，宽度为 n 的长条内的最大值，和第一次的预处理差不多，只是行列颠倒了。这样我们就能求出每列中“每行中元素最大值”（就是 maxn）的最大值了。然后这个结果就是正方形块内的最大值。

时间 O(ab)。

:::info[以样例为例的所有数组]

a=5,b=4,n=2;
输入的p[i][j]
 1  2  5  6
 0 17 16  0
16 17  2  1
 2 10  2  1
 1  2  2  2
以(i,j)为右端点，长度为n的长条内的最值
maxn[i][j]     minn[i][j]
-1  2  5  6    -1  1  2  5
-1 17 17 16    -1  0 16  0
-1 17 17  2    -1 16  2  1
-1 10 10  2    -1  2  2  1
-1  2  2  2    -1  1  2  2
以(i,j)为右下角，边长为n的正方形内的最值
maxl[i][j]     minl[i][j]
-1 -1 -1 -1    -1 -1 -1 -1
-1 17 17 16    -1  0  2  0
-1 17 17 16    -1  0  2  0
-1 17 17  2    -1  2  2  1
-1 10 10  2    -1  1  2  1
“-1”代表无法构造长条或正方形

:::

:::

我表达能力怎么这么差， 看代码吧，自认为马蜂良好。

Code

:::success[by elainya_stars]

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fastio ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define nbsp cerr<<'\n'
#define debugx(x) cerr<<#x<<" : "<<x<<'\n'
#define debuga(x,l,r) cerr<<#x<<" : ";for(int i=l;i<=r;i++)cerr<<x[i]<<' ';cerr<<'\n'
#define debugp(x,i) cerr<<#x<<'['<<i<<']'<<" : "<<x[i]<<'\n'
#define flin(s) char ccccc1[100]=s;char ccccc2[5]=".in";freopen(strcat(ccccc1,ccccc2),"r",stdin)
#define flout(s) char ccccc3[100]=s;char ccccc4[5]=".out";freopen(strcat(ccccc3,ccccc4),"w",stdout)
#define clr(x,y) memset(x,y,sizeof x)

const int N=1005,inf=0x3f3f3f3f3f3f3f3f;
int a,b,n,p[N][N],maxn[N][N],minn[N][N];
// maxn minn用来存第一次预处理的结果：
// 以(i,j)为右端点，长度为n的长条内的最大最小值
int maxl[N][N],minl[N][N];
// maxl minl用来存第二次预处理的结果：
// 以(i,j)为右下角，边长为n的正方形内的最大最小值
struct queue_ // 手搓队列
{
    int ll=1,rr,a[N];
    void pushl(int x) {a[++ll]=x;}
    void pushr(int x) {a[++rr]=x;}
    void popl() {ll++;}
    void popr() {rr--;}
    int l() {return a[ll];}
    int r() {return a[rr];}
    bool empty() {return ll>rr;}
}q;

signed main()
{
    fastio;
    cin>>a>>b>>n;
    for(int i=1;i<=a;i++)
        for(int j=1;j<=b;j++)
            cin>>p[i][j];
    clr(maxn,-1),clr(minn,-1),clr(maxl,-1),clr(minl,-1);
    // 全赋-1，因为元素有可能为0
    for(int i=1;i<=a;i++) // 行下标
    {
        q.ll=1,q.rr=0; // 清队
        for(int j=1;j<=b;j++)
        {
            while(!q.empty() && q.l()<j-n+1)
                q.popl();
            while(!q.empty() && p[i][q.r()]<=p[i][j])
                q.popr();
            q.pushr(j);
            // 上面单调队列板子
            if(j>=n) // 小于n时不可构造长条，值还为-1
                maxn[i][j]=p[i][q.l()]; // 赋值
        }
        q.ll=1,q.rr=0; // 同理
        for(int j=1;j<=b;j++)
        {
            while(!q.empty() && q.l()<j-n+1)
                q.popl();
            while(!q.empty() && p[i][q.r()]>=p[i][j])
                q.popr();
            q.pushr(j);
            if(j>=n)
                minn[i][j]=p[i][q.l()];
        }
    }
    for(int j=1;j<=b;j++) // 列下标
    {
        if(maxn[1][j]==-1) // 如果为-1，不可构造正方形
            continue;
        q.ll=1,q.rr=0; // 和上面同理，行列颠倒
        for(int i=1;i<=a;i++)
        {
            while(!q.empty() && q.l()<i-n+1)
                q.popl();
            while(!q.empty() && maxn[q.r()][j]<=maxn[i][j])
                q.popr();
            q.pushr(i);
            if(i>=n)
                maxl[i][j]=maxn[q.l()][j];
        }
        q.ll=1,q.rr=0;
        for(int i=1;i<=a;i++)
        {
            while(!q.empty() && q.l()<i-n+1)
                q.popl();
            while(!q.empty() && minn[q.r()][j]>=minn[i][j])
                q.popr();
            q.pushr(i);
            if(i>=n)
                minl[i][j]=minn[q.l()][j];
        }
    }
    int ans=inf;
    for(int i=1;i<=a;i++)
        for(int j=1;j<=b;j++)
        {
            if(maxl[i][j]==-1) // 若为-1，不可构造正方形
                continue;
            ans=min(ans,maxl[i][j]-minl[i][j]);
        }
    cout<<ans<<'\n';
    return (0.0);
}

:::

给我赞赞 qwq