【单调队列】bzoj 1407 [HAOI2007]理想的正方形

【题意】

给定一个n*m的矩阵，求所有大小为k*k的正方形中(最大值-最小值)的最小值

【思路】

先横着算出每一行的长度为k的窗口内的最大值，变成一个n*(m-k+1)的矩阵mx
再竖着算出每一列的长度为k的窗口内的最大值，变成一个(n-k+1)*(m-k+1)的矩阵t1（在mx的基础上算）
问题到这里转化为裸的单调队列
最小值同理
时间复杂度为O(n*m)
转自http://www.cnblogs.com/szy-wlxy/p/4631700.html

【AC】

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 inline int read()
  5 {
  6     int x=0,f=1;char ch=getchar();
  7     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
  8     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
  9     return x*f;
 10 }
 11 
 12 int n,m,k;
 13 const int maxn=1e3+2;
 14 int a[maxn][maxn];
 15 int mx[maxn][maxn];
 16 int mn[maxn][maxn];
 17 int t1[maxn][maxn];
 18 int t2[maxn][maxn];
 19 struct node
 20 {
 21     int x;
 22     int pos;
 23     node(){}
 24     node(int _x,int _pos):x(_x),pos(_pos){}
 25 }q[maxn];
 26 void pre()
 27 {
 28     for(int i=1;i<=n;i++)
 29     {
 30         //max 
 31         int head=1,tail=0;
 32         for(int j=1;j<=m;j++)
 33         {
 34             while(tail>=head&&q[tail].x<=a[i][j])
 35                  tail--;
 36             q[++tail].x=a[i][j],q[tail].pos=j;
 37             while(q[head].pos<=j-k)
 38                  head++;
 39             if(j>=k) 
 40                 mx[i][j]=q[head].x;
 41         }
 42         //min
 43         head=1,tail=0;
 44         for(int j=1;j<=m;j++)
 45         {
 46             while(tail>=head&&q[tail].x>=a[i][j])
 47                  tail--;
 48             q[++tail].x=a[i][j],q[tail].pos=j;
 49             while(q[head].pos<=j-k)
 50                  head++;
 51             if(j>=k) 
 52                 mn[i][j]=q[head].x;
 53         }
 54     }
 55 }
 56 void solve()
 57 {
 58     for(int j=k;j<=m;j++)
 59     {
 60         int head=1,tail=0;
 61         for(int i=1;i<=n;i++)
 62         {
 63             while(tail>=head&&q[tail].x<=mx[i][j])
 64                  tail--;
 65             q[++tail].x=mx[i][j],q[tail].pos=i;
 66             while(q[head].pos<=i-k)
 67                  head++;
 68             if(i>=k) 
 69                 t1[i][j]=q[head].x;
 70         }
 71     }
 72     for(int j=k;j<=m;j++)
 73     {
 74         int head=1,tail=0;
 75         for(int i=1;i<=n;i++)
 76         {
 77             while(tail>=head&&q[tail].x>=mn[i][j])
 78                  tail--;
 79             q[++tail].x=mn[i][j],q[tail].pos=i;
 80             while(q[head].pos<=i-k)
 81                  head++;
 82             if(i>=k) 
 83                 t2[i][j]=q[head].x;
 84         }
 85     }
 86     int ans;
 87     for(int i=k;i<=n;i++)
 88     {
 89         for(int j=k;j<=m;j++)
 90         {
 91             if(i==k&&j==k) ans=t1[i][j]-t2[i][j];
 92             else ans=min(ans,t1[i][j]-t2[i][j]);    
 93         }
 94     }
 95     printf("%d
",ans);
 96 }
 97 int main()
 98 {
 99     n=read();m=read();k=read();
100     for(int i=1;i<=n;i++)
101     {
102         for(int j=1;j<=m;j++)
103         {
104             a[i][j]=read();
105         }
106     }
107     pre();
108     solve();
109     return 0;
110 }

单调队列