bzoj1047

二维单调队列

rmq很明显会超时，如果这个序列是一维的，很明显就是个单调队列，现在就是把一维的单调队列转换为二维单调队列。

先求出每一列的窗口极值，然后对于每一行做单调队列，值就是之前求出每个位置结尾的极值，这样就求出了每个正方形的极值。

写起来要注意一些。

#include<bits/stdc++.h>

using namespace std;

const int N = ;

int a, b, n, ans =  << ;

int d[N][N], mx[N][N], mn[N][N], q1[N], q2[N], mxx[N][N], mnn[N][N];

int main()

{

//  freopen("square.in", "r", stdin);

//  freopen("square.out", "w", stdout);

    scanf("%d%d%d", &a, &b, &n);

    for(int i = ; i <= a; ++i)

        for(int j = ; j <= b; ++j) scanf("%d", &d[i][j]);

    for(int i = ; i <= a; ++i)

    {

        int l1 = , r1 = , l2 = , r2 = ;

        for(int j = ; j <= b; ++j)

        {

            while(l1 <= r1 && j - q1[l1] +  > n) ++l1;

            while(l1 <= r1 && d[i][j] > d[i][q1[r1]]) --r1;

            while(l2 <= r2 && j - q2[l2] +  > n) ++l2;

            while(l2 <= r2 && d[i][j] < d[i][q2[r2]]) --r2;

            q1[++r1] = j;

            q2[++r2] = j;

            mx[i][j] = d[i][q1[l1]];

            mn[i][j] = d[i][q2[l2]];

//          printf("mx[%d][%d]=%d mn[%d][%d]=%d\n", i, j, mx[i][j], i, j, mn[i][j]);

        }

    }

    for(int j = n; j <= b; ++j)

    {

        int l1 = , r1 = , l2 = , r2 = ;

        for(int i = ; i <= a; ++i)

        {

            while(l1 <= r1 && i - q1[l1] +  > n) ++l1;

            while(l1 <= r1 && mx[i][j] > mx[q1[r1]][j]) --r1;

            while(l2 <= r2 && i - q2[l2] +  > n) ++l2;

            while(l2 <= r2 && mn[i][j] < mn[q2[r2]][j]) --r2;

            q1[++r1] = i;

            q2[++r2] = i;

            mxx[i][j] = mx[q1[l1]][j];

            mnn[i][j] = mn[q2[l2]][j];

//          printf("mxx[%d][%d]=%d mnn[%d][%d]=%d\n", i, j, mxx[i][j], i, j, mnn[i][j]);

        }

    }

    for(int i = n; i <= a; ++i)

        for(int j = n; j <= b; ++j) ans = min(ans, mxx[i][j] - mnn[i][j]);

    printf("%d\n", ans);

//  fclose(stdin);

//  fclose(stdout);

    return ;

}