其实如果空间再大一点可以用二维ST表,但可惜空间太小了
于是就用二维单调队列先处理一维,再转到二维
二维ST表解法 代码
//#pragma GCC optimize(3,"inline","Ofast","fast-math","no-stack-protector","unroll-loops")
//#pragma GCC target("sse","sse2","sse3","sse4","avx","avx2","popcnt")
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#define RG register
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const int N=1e3+10;
int a,b,n;
int f[3][N][N][13],p[N][N],Log[N];
inline int max(int u,int x,int y,int z)
{
int kl=u;if(kl<x) kl=x;if(kl<y) kl=y;if(kl<z) kl=z;
return kl;
}
inline int min(int u,int x,int y,int z)
{
int kl=u;if(kl>x) kl=x;if(kl>y) kl=y;if(kl>z) kl=z;
return kl;
}
inline void init()
{
for (int i=2;i<=n;i++) Log[i]=Log[i/2]+1;
for (int i=1;i<=a;i++)
for (int j=1;j<=b;j++)
f[0][i][j][0]=f[1][i][j][0]=p[i][j];
for (int k=1;k<=12;k++)
for (int i=1;i+(1<<k)-1<=a;i++)
for (int j=1;j+(1<<k)-1<=b;j++)
{
int t1=f[0][i][j][k-1];
int t2=f[0][i+(1<<k-1)][j][k-1];
int t3=f[0][i][j+(1<<k-1)][k-1];
int t4=f[0][i+(1<<k-1)][j+(1<<k-1)][k-1];
f[0][i][j][k]=max(t1,t2,t3,t4);
t1=f[1][i][j][k-1];
t2=f[1][i+(1<<k-1)][j][k-1];
t3=f[1][i][j+(1<<k-1)][k-1];
t4=f[1][i+(1<<k-1)][j+(1<<k-1)][k-1];
f[1][i][j][k]=min(t1,t2,t3,t4);
}
}
inline int find(int x,int y)
{
int k=Log[n];
int t1=f[0][x][y][k];
int t2=f[0][x+n-(1<<k)][y][k];
int t3=f[0][x+n-(1<<k)][y+n-(1<<k)][k];
int t4=f[0][x][y+n-(1<<k)][k];
int mx=max(t1,t2,t3,t4);
t1=f[1][x][y][k];
t2=f[1][x+n-(1<<k)][y][k];
t3=f[1][x+n-(1<<k)][y+n-(1<<k)][k];
t4=f[1][x][y+n-(1<<k)][k];
int mi=min(t1,t2,t3,t4);
return mx-mi;
}
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",&p[i][j]);
init();
int ans=INF;
for (int i=1;i<=a-n+1;i++)
for (int j=1;j<=b-n+1;j++)
{
int k=find(i,j);
if(k<ans) ans=k;
}
printf("%d\n",ans);
return 0;
}
单调队列 代码
//#pragma GCC optimize(3,"inline","Ofast","fast-math","no-stack-protector","unroll-loops")
//#pragma GCC target("sse","sse2","sse3","sse4","avx","avx2","popcnt")
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#define RG register
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const int N=1e3+10;
int n,m,len;
int q[N],Q[N];
int a[N][N],b[N][N],k[N][N],d[N][N],f[N][N];
int main()
{
scanf("%d%d%d",&n,&m,&len);
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=1,r=0,L=1,R=0;
for (int j=1;j<=m;j++)
{
while(l<=r&&q[l]<j-len+1) l++;
while(l<=r&&a[i][j]>=a[i][q[r]]) r--;
q[++r]=j;
b[i][j]=a[i][q[l]];
while(L<=R&&Q[L]<j-len+1) L++;
while(L<=R&&a[i][j]<=a[i][Q[R]]) R--;
Q[++R]=j;
d[i][j]=a[i][Q[L]];
}
}//点动成线
for (int i=1;i<=m;i++)
{
int l=1,r=0,L=1,R=0;
for (int j=1;j<=n;j++)
{
while(l<=r&&q[l]<j-len+1) l++;
while(l<=r&&b[q[r]][i]<=b[j][i]) r--;
q[++r]=j;
k[j][i]=b[q[l]][i];
while(L<=R&&Q[L]<j-len+1) L++;
while(L<=R&&d[Q[R]][i]>=d[j][i]) R--;
Q[++R]=j;
f[j][i]=d[Q[L]][i];
}
}
int ans=INF;
for (int i=len;i<=n;i++)
for (int j=len;j<=m;j++)
{
ans=min(ans,k[i][j]-f[i][j]);
}
printf("%d\n",ans);
return 0;
}
tql
受宠若惊
#tql