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);
}