[HAOI2007 理想的正方形]单调队列

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1047
【算法分析】
先弄一个dmax[i][j]和dmin[i][j]数组分别表示(i,j)这个点往下的n（是题目中的n）个点中，最大值（最小值）是多少。然后这样压缩以后横向再来一次就可以。
【其它】
看到群里说2维单调队列，然后师傅就发了这个链接。。。
难道这就是传说中的2维
还以为是很恐怖的东西。。。
【其它】1Y。
【CODE】
#include #include #include #include using namespace std;
const int N=1005;
int m,n,L,i,j,head,tail;
int w[N][N],dmax[N][N],dmin[N][N],a[N][N],b[N][N],qp[N],qf[N];

int main(){
scanf("%d%d%d",&m,&n,&L);
for (i=1;i<=m;i++)
for (j=1;j<=n;j++)
scanf("%d",&w[i][j]);
for (j=1;j<=n;j++){
head=1; tail=0;
for (i=1;i while (head<=tail && w[i][j]>qf[tail]) tail--;
qf[++tail]=w[i][j]; qp[tail]=i;
}
for (i=1;i+L-1<=m;i++){
while (head<=tail && w[i+L-1][j]>qf[tail]) tail--;
qf[++tail]=w[i+L-1][j]; qp[tail]=i+L-1;
while (qp[head] dmax[i][j]=qf[head];
}
}

for (j=1;j<=n;j++){
head=1; tail=0;
for (i=1;i while (head<=tail && w[i][j] qf[++tail]=w[i][j]; qp[tail]=i;
}
for (i=1;i+L-1<=m;i++){
while (head<=tail && w[i+L-1][j] qf[++tail]=w[i+L-1][j]; qp[tail]=i+L-1;
while (qp[head] dmin[i][j]=qf[head];
}
}
int ans=0x7FFFFFFF;
for (i=1;i+L-1<=m;i++){
head=1; tail=0;
for (j=1;j<=n;j++){
while (head<=tail && dmax[i][j]>qf[tail]) tail--;
qf[++tail]=dmax[i][j]; qp[tail]=j;
while (qp[head]<=j-L) head++;
a[i][j]=qf[head];
}
head=1; tail=0;
for (j=1;j<=n;j++){
while (head<=tail && dmin[i][j] qf[++tail]=dmin[i][j]; qp[tail]=j;
while (qp[head]<=j-L) head++;
b[i][j]=qf[head];
}
}
for (i=1;i+L-1<=m;i++)
for (j=L;j<=n;j++)
ans=min(ans,a[i][j]-b[i][j]);
printf("%dn",ans);
}