【二维单调队列】BZOJ1047-[HAOI2007]理想的正方形

【题目大意】

有一个a*b的整数组成的矩阵，现请你从中找出一个n*n的正方形区域，使得该区域所有数中的最大值和最小值的差最小。

【思路】

裸的二维单调队列。二维单调队列的思路其实很简单:

(1)对于每一行维护两个宽度为n的滑动窗口记录单行中的min和max，和POJ2823一个道理。此时相当于把n个格子浓缩到了一个格子当中。

(2)维护n*n大小的二维滑动窗口中的min和max。由于有了第一步操作，只要考虑每一个n*n的矩形右上角到右下角的最值即可。相当于对于每一列，维护两个宽度为n的滑动窗口。此时循环要行和列里外颠倒，而列只要从第n列开始维护即可（我一开始就错在了这两个地方）

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define INF 0x7fffffff
 6 struct node
 7 {
 8     int data,pos;
 9 };
10 using namespace std;
11 const int MAXN=1000+50;
12 int a,b,n;
13 int num[MAXN][MAXN];
14 int rmin[MAXN][MAXN],rmax[MAXN][MAXN],smin[MAXN][MAXN],smax[MAXN][MAXN];
15 
16 void init()
17 {
18     scanf("%d%d%d",&a,&b,&n);
19     for (int i=0;i<a;i++)
20         for (int j=0;j<b;j++) scanf("%d",&num[i][j]);
21 }
22 
23 void humdrum_queue()
24 {
25     /*对于每一行，用单调队列维护[x-n+1,x]的最小值和最大值*/
26     for (int i=0;i<a;i++)
27     {
28         int minhead=0,mintail=0,maxhead=0,maxtail=0;
29         node qmin[MAXN],qmax[MAXN];
30         for (int j=0;j<b;j++)
31         {
32             int nown=num[i][j];
33             /*维护最小值*/
34             while (minhead<mintail && qmin[mintail-1].data>nown) mintail--;
35             qmin[mintail++]=(node){nown,j};
36             while (minhead<mintail && qmin[minhead].pos<=j-n) minhead++;
37             rmin[i][j]=qmin[minhead].data;
38             
39             /*维护最大值*/
40             while (maxhead<maxtail && qmax[maxtail-1].data<nown) maxtail--;
41             qmax[maxtail++]=(node){nown,j};
42             while (maxhead<maxtail && qmax[maxhead].pos<=j-n) maxhead++;
43             rmax[i][j]=qmax[maxhead].data;
44         }
45     }
46     
47     /*对于以[i,j]为右下角的n*n矩形，用单调队列维护它的最小值和最大值
48       这步操作可以用单调队列维护每一列，相当于维护该矩形右上角到右下角对应点的rmin与rmax值*/
49     /*|ATTENTION|要注意的是这里i和j要颠倒过来，所以内外循环以及队列中的pos均要颠倒！*/
50     for (int j=n-1;j<b;j++)
51     {
52         int minhead=0,mintail=0,maxhead=0,maxtail=0;
53         node qmin[MAXN],qmax[MAXN];
54           for (int i=0;i<a;i++)
55         {
56             int nowmin=rmin[i][j],nowmax=rmax[i][j];
57             /*维护最小值*/
58             while (minhead<mintail && qmin[mintail-1].data>nowmin) mintail--;
59             qmin[mintail++]=(node){nowmin,i};
60             while (minhead<mintail && qmin[minhead].pos<=i-n) minhead++;
61             smin[i][j]=qmin[minhead].data;
62             
63             /*维护最大值*/
64             while (maxhead<maxtail && qmax[maxtail-1].data<nowmax) maxtail--;
65             qmax[maxtail++]=(node){nowmax,i};
66             while (maxhead<maxtail && qmax[maxhead].pos<=i-n) maxhead++;
67             smax[i][j]=qmax[maxhead].data;
68         }
69     }
70 }
71 
72 void getans()
73 {
74     int ans=INF;
75     for (int i=n-1;i<a;i++)
76         for (int j=n-1;j<b;j++)
77             if (smax[i][j]-smin[i][j]<ans) ans=smax[i][j]-smin[i][j];
78     cout<<ans<<endl;
79 }
80 
81 int main()
82 {
83      init();
84      humdrum_queue();
85      getans();
86      return 0;
87 }