bzoj1047: [HAOI2007]理想的正方形

单调队列压缩每一行的最大最小，再压缩每一列，然后暴力a*b求答案

const int N = 1010;
int Data[N][N], n, m, Len;

inline void Input() {
	scanf("%d%d%d", &n, &m, &Len);
	For(i, 1, n)
		For(j, 1, m) scanf("%d", &Data[i][j]);
}

int Cnt[N][N][2], T[N][N][2]; //0->max 1->min
int Sex[N], Lef, Rig;

inline bool Cmp(int Type, int A, int B) {
	return (A < B) == Type;
}
inline void Solve() {
	// row
	For(i, 1, n)
		Rep(Type, 2) {
			Lef = 1, Rig = 0;
			Ford(j, m, 1) {
				while(Rig >= Lef && Cmp(Type, Data[i][j], Data[i][Sex[Rig]])) Rig--;
				Sex[++Rig] = j;
				while(Lef <= Rig && Sex[Lef] - j + 1 > Len) Lef++;
				
				if(j <= m - Len + 1) T[i][j][Type] = Data[i][Sex[Lef]];
			}
		}
	
	// line
	For(i, 1, m)
		Rep(Type, 2) {
			Lef = 1, Rig = 0;
			Ford(j, n, 1) {
				while(Rig >= Lef && Cmp(Type, T[j][i][Type], T[Sex[Rig]][i][Type])) Rig--;
				Sex[++Rig] = j;
				while(Lef <= Rig && Sex[Lef] - j + 1 > Len) Lef++;
				
				if(j <= n - Len + 1) Cnt[j][i][Type] = T[Sex[Lef]][i][Type];
			}
		}
	
	// debug
	
	int Ans = MIT;
	For(i, 1, n - Len + 1)
		For(j, 1, m - Len + 1) Ans = min(Ans, Cnt[i][j][0] - Cnt[i][j][1]);
	printf("%d\n", Ans);
}

int main() {
	#ifndef ONLINE_JUDGE
	SETIO("1047");
	#endif
	Input();
	Solve();
	return 0;
}