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

时间：2023-03-08 15:53:01
Luogu 2216[HAOI2007]理想的正方形 - 单调队列

Solution

二维单调队列， 这个数组套起来看得我眼瞎。。。

Code

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define rd read()

 #define rep(i,a,b) for(register int i = (a); i <= (b); ++i)

 #define per(i,a,b) for(register int i = (a); i >= (b); --i)

 #define Lb lb[i]

 #define Rb rb[i]

 #define Ls ls[i]

 #define Rs rs[i]

 using namespace std;

 const int N = 1e3 + ;

 const int inf = ~0U >> ;

 int n, m, len, a[N][N];

 int qb[N][N], lb[N], rb[N];

 int qs[N][N], ls[N], rs[N];

 int qB[N], LB, RB;

 int qS[N], LS, RS;

 int ans = inf;

 int read() {

     int X = , p = ; char c = getchar();

     for(; c > '' || c < ''; c = getchar()) if(c == '-') p = -;

     for(; c >= '' && c <= ''; c = getchar()) X = X *  + c - '';

     return X * p;

 }

 int main()

 {

     n = rd; m = rd; len = rd;

     rep(i, , n) rep(j, , m) a[i][j] = rd;

     rep(i, , n) ls[i] = lb[i] = ;

     rep(j, , m) {

         rep(i, , n) {

             while(qb[i][Lb] <= j - len && Lb <= Rb) Lb++;

             while(qs[i][Ls] <= j - len && Ls <= Rs) Ls++;

             while(Lb <= Rb && a[i][qb[i][Rb]] <= a[i][j]) Rb--;

             while(Ls <= Rs && a[i][qs[i][Rs]] >= a[i][j]) Rs--;

             qb[i][++Rb] = j;

             qs[i][++Rs] = j;

         }

         LS = LB = ;

                 RB = RS = ;

                 if(j >= len)

         rep(i, , n) {

             while(qB[LB] <= i - len && LB <= RB) LB++;

             while(qS[LS] <= i - len && LS <= RS) LS++;

             while(LB <= RB && a[qB[RB]][qb[qB[RB]][lb[qB[RB]]]] <= a[i][qb[i][Lb]]) RB--;

             while(LS <= RS && a[qS[RS]][qs[qS[RS]][ls[qS[RS]]]] >= a[i][qs[i][Ls]]) RS--;

             qB[++RB] = i;

             qS[++RS] = i;

                         int hb = qB[LB], hs = qS[LS];

                         if(i >= len) ans = min(ans, a[hb][qb[hb][lb[hb]]] - a[hs][qs[hs][ls[hs]]]);

         }

     }

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

 }

相关文章