二维单调队列或st表

模板题 ：[HAOI2007]理想的正方形
题目链接：https://www.luogu.com.cn/problem/P2216
二维st表或二维单调队列。
单调队列做法:
Code:

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int a,b,n,num[N][N],q[N],fnmx[N][N],fnmn[N][N];
int datmin[N][N],datmax[N][N],fucker[N],ans=INT_MAX;
void solve1(int x){
	int l=1,r=0,*c=num[x];
	for(int i=1;i<=b;i++){
		while(l<=r&&c[i]<c[q[r]])r--;
		q[++r]=i;
		while(l<=r&&i-q[l]>=n)l++;
		if(i>=n)datmin[x][i]=c[q[l]];
	} 
	return;
}
void solve2(int x){
	int l=1,r=0,*c=num[x];
	for(int i=1;i<=b;i++){
		while(l<=r&&c[i]>c[q[r]])r--;
		q[++r]=i;
		while(l<=r&&i-q[l]>=n)l++;
		if(i>=n)datmax[x][i]=c[q[l]];
	}
	return;
}
void solve3(int x){
	int l=1,r=0;
	for(int i=1;i<=a;i++)
		fucker[i]=datmax[i][x];
	for(int i=1;i<=a;i++){
		while(l<=r&&fucker[i]>fucker[q[r]])r--;
		while(l<=r&&i-q[l]>=n)l++;
		q[++r]=i;
		if(i>=n)fnmx[i][x]=fucker[q[l]];
	}
	return;	
}
void solve4(int x){
	int l=1,r=0;
	for(int i=1;i<=a;i++)
		fucker[i]=datmin[i][x];
	for(int i=1;i<=a;i++){
		while(l<=r&&fucker[i]<fucker[q[r]])r--;
		while(l<=r&&i-q[l]>=n)l++;
		q[++r]=i;
		if(i>=n)fnmn[i][x]=fucker[q[l]];
	}
	return;	
} 
int main(){
	scanf("%d%d%d",&a,&b,&n);
	for(int i=1;i<=a;i++)
		for(int j=1;j<=b;j++)
			scanf("%d",&num[i][j]);
	for(int i=1;i<=a;i++)solve1(i),solve2(i);
	for(int i=b;i>=n;i--)solve3(i),solve4(i);
	for(int i=1;i<=a;i++)
		for(int j=1;j<=b;j++)
			if(fnmx[i][j]&&fnmn[i][j])ans=min(fnmx[i][j]-fnmn[i][j],ans);
	printf("%d",ans);
	return 0;
}

二维st表：

#include<bits/stdc++.h>
using namespace std;
const int INF=2147483647,N=1e3+5;
int n,m,k,K,grid[N][N],dv[N][N],xv[N][N];
int query(int x, int y){
    int mx=0,mn=0;
    mx=max(dv[x][y],max(dv[x+k-(1<<K)][y+k-(1<<K)],max(dv[x+k-(1<<K)][y],dv[x][y+k-(1<<K)])));
    mn=min(xv[x][y],min(xv[x+k-(1<<K)][y+k-(1<<K)],min(xv[x+k-(1<<K)][y],xv[x][y+k-(1<<K)])));
    return mx-mn;
}
int main (){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            scanf("%d",&grid[i][j]);
            dv[i][j]=xv[i][j]=grid[i][j];
        }    	
	K=floor(log2(k));
    for(int s=0;s<=K-1;s++)
        for(int i=1;i+(1<<s)<=n;i++)
            for(int j=1;j+(1<<s)<=m;j++){
                dv[i][j]=max(dv[i][j],max(dv[i+(1<<s)][j+(1<<s)],max(dv[i+(1<<s)][j],dv[i][j+(1<<s)])));
                xv[i][j]=min(xv[i][j],min(xv[i+(1<<s)][j+(1<<s)],min(xv[i+(1<<s)][j],xv[i][j+(1<<s)])));	
	        }
    int ans=INF;
    for(int i=1;i<=n-k+1;i++)
        for(int j=1;j<=m-k+1;j++)ans=min(ans,query(i,j));
	printf("%d\n",ans);
    return 0;
}