题目链接
Solution
MD,经过这道题,算是掌握单调队列了...
可以先预处理出点 \((i,j)\) 往上 \(n\) 的最大值和最小值.
然后再横着做一遍单调队列即可.
Code
#include<bits/stdc++.h>
#define in(x) x=read();
#define ll long long
#define N 1001
using namespace std;
ll read()
{
char ch=getchar(); ll f=1,w=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){w=w*10+ch-'0';ch=getchar();}
return f*w;
}
ll Mx[N][N],Mn[N][N];
ll a,n,m,w[N][N];
ll ans=0x3f3f3f3f3f;
int main()
{
in(n); in(m); in(a);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
in(w[i][j]);
for(int j=1;j<=m;j++)
{
int head=1,tail=0,q[N];
for(int i=1;i<=n;i++)
{
while(head<=tail&&w[q[tail]][j]>=w[i][j]) tail--;
q[++tail]=i;
while(q[tail]-q[head]>=a) head++;
Mn[j][i]=w[q[head]][j];
}
head=1;tail=0;
for(int i=1;i<=n;i++)
{
while(head<=tail&&w[q[tail]][j]<=w[i][j]) tail--;
q[++tail]=i;
while(q[tail]-q[head]>=a) head++;
Mx[j][i]=w[q[head]][j];
}
}
for(int i=a;i<=n;i++)
{
int h=1,t=0,H=1,T=0;
ll minn,maxx,q1[N],q2[N];
for(int j=1;j<=m;j++)
{
while(h<=t&&Mn[q1[t]][i]>=Mn[j][i]) t--;
while(H<=T&&Mx[q2[T]][i]<=Mx[j][i]) T--;
q1[++t]=j;q2[++T]=j;
while(q1[t]-q1[h]>=a) h++;
while(q2[T]-q2[H]>=a) H++;
minn=Mn[q1[h]][i];
maxx=Mx[q2[H]][i];
if(j>=a)
ans=min(ans,maxx-minn);
}
}
cout<<ans;
}