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

· · 题解

其实算是一道 ds 吧。

题意

有一个 a\times b 的矩阵，要找出一个 n\times n 的矩阵，使其里面的最大值与最小值的差最小，并输出差值。

Solution

发现有最大值问题与最小值问题，考虑二维 ST 表。

令 st_{k,i,j} 为以 (i,j) 为左上角，大小 2^k \times 2^k 的正方形的最值。

预处理

我们可以分别把长和宽拆成 2^{k-1}+2^{k-1}，所以可以得到：

st_{k,i,j}=\max\left\{\begin{matrix}st_{k-1,i,j} \\st_{k-1,i,j+2^{k-1}} \\st_{k-1,i+2^{k-1},j} \\st_{k-1,i+2^{k-1},j+2^{k-1}} \end{matrix}\right.

查询

假设要求左上角 (x1,y1)，右下角 (x2,y2) 的正方形的最值。 令 k=\lfloor \log_2 L \rfloor。这里 L 是正方形的边长。依旧把长和宽拆成 2^{k-1}+2^{k-1}，可以得到所求值应为：

Ans=\max\left\{\begin{matrix}st_{k,x1,y1} \\st_{k,x1,y2-2^k+1} \\st_{k,x2-2^k+1,y1} \\st_{k,x2-2^k+1,y2-2^k+1} \end{matrix}\right.

时间复杂度

二维 ST 表，不难根据一维来推出是 O(n^2 \log n)。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=1050;
int a,b,n;
int stmax[15][N][N],stmin[15][N][N];
int ans=0x3f3f3f3f;
int lg[N];
void init(){
    for(int i=2;i<=N;i++){
        lg[i]=lg[i/2]+1;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>a>>b>>n;
    init();
    for(int i=1;i<=a;i++){
        for(int j=1;j<=b;j++){
            int x;
            cin>>x;
            stmax[0][i][j]=stmin[0][i][j]=x;
        }
    }   
    for(int k=1;k<=lg[min(a,b)];k++){
        for(int i=1;i+(1<<k)-1<=a;i++){
            for(int j=1;j+(1<<k)-1<=b;j++){
                stmax[k][i][j]=max({stmax[k-1][i][j],stmax[k-1][i][j+(1<<k-1)],stmax[k-1][i+(1<<k-1)][j],stmax[k-1][i+(1<<k-1)][j+(1<<k-1)]});
                stmin[k][i][j]=min({stmin[k-1][i][j],stmin[k-1][i][j+(1<<k-1)],stmin[k-1][i+(1<<k-1)][j],stmin[k-1][i+(1<<k-1)][j+(1<<k-1)]});
            }
        }
    }   
    for(int i=1;i+n-1<=a;i++){
        for(int j=1;j+n-1<=b;j++){
            int k=lg[n];
            int maxn=max({stmax[k][i][j],stmax[k][i][j+n-(1<<k)],stmax[k][i+n-(1<<k)][j],stmax[k][i+n-(1<<k)][j+n-(1<<k)]});
            int minn=min({stmin[k][i][j],stmin[k][i][j+n-(1<<k)],stmin[k][i+n-(1<<k)][j],stmin[k][i+n-(1<<k)][j+n-(1<<k)]});
            ans=min(ans,maxn-minn);
        }
    }   
    cout<<ans;
    return 0;
}