[BZOJ 1047][HAOI 2007]理想的正方形(二維滑動窗口+單調隊列)

[BZOJ 1047][HAOI 2007]理想的正方形(二維滑動窗口+單調隊列)

思路：裸的二維上的滑動窗口問題，可以借鑒一維滑動窗口的思路。首先預處理出每一列j的、以第i行元素為結尾、長度為n的區間的最大值maxv[i][j]、最小值minv[i][j]，然後再搞每一行，求出以每一行i結尾、行標上長度為n的區間、以第j列結尾、列標上長度為n的區間得到的二維區間最大值與最小值之差，遍歷每一行得到這個差的最小值即為答案。

#include 
#include 
#include 
#include 
#include 

#define MAXN 1200
#define INF 0x3f3f3f3f

using namespace std;

struct node
{
    int val; //這個元素的值
    int pos; //這個元素的下標
}q1[MAXN],q2[MAXN]; //q1維護一個單調遞減隊列，q2維護一個單調遞增對了隊列

int map[MAXN][MAXN];
int maxv[MAXN][MAXN],minv[MAXN][MAXN];
int pa,pb,n; //pa*pb大小的矩陣,從中取n*n大小的子矩陣

void init()
{
    scanf(%d%d%d,&pa,&pb,&n);
    for(int i=1;i<=pa;i++)
        for(int j=1;j<=pb;j++)
            scanf(%d,&map[i][j]);
}

void work1() //第一次操作維護每一列的最值，最終得到第j列以第i個元素結尾的長度為n的區間的最大值、最小值
{
    int h1,t1,h2,t2; //隊尾與隊首的指針
    for(int j=1;j<=pb;j++) //枚舉列號j
    {
        h1=h2=t1=t2=0;
        for(int i=1;i<=pa;i++) //枚舉長度為n的區間的最後一個元素下標i,當前長度為n的區間為[i-n+1,i
        {
            //維護隊列q1
            while(h1=map[i][j]) //把隊尾不滿足單調性的都彈掉
                t2--;
            q2[++t2].val=map[i][j];
            q2[t2].pos=i;
            if(i=minv[i][j]) //把隊尾不滿足單調性的都彈掉
                t2--;
            q2[++t2].val=minv[i][j];
            q2[t2].pos=j;
            if(i>=n&&j>=n)
                ans=min(ans,q1[h1+1].val-q2[h2+1].val);
        }
    }
    printf(%d
,ans);
}

int main()
{
    init();
    work1();
    work2();
    return 0;
}