1604：理想的正方形

// 1604：理想的正方形.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <deque>
#include <algorithm>

using namespace std;
/*
https://loj.ac/p/10182
http://ybt.ssoier.cn:8088/problem_show.php?pid=1604

原题来自：HAOI 2007

有一个 a×b
 的整数组成的矩阵，现请你从中找出一个 n×n
 的正方形区域，使得该区域所有数中的最大值和最小值的差最小。

【输入】
第一行为三个整数，分别表示 a,b,n
 的值；

第二行至第 a+1
 行每行为 b
 个非负整数，表示矩阵中相应位置上的数。

【输出】
输出仅一个整数，为 a×b
 矩阵中所有「n×n
 正方形区域中的最大整数和最小整数的差值」的最小值。

【输入样例】
5 4 2
1 2 5 6
0 17 16 0
16 17 2 1
2 10 2 1
1 2 2 2
【输出样例】
1


2≤a,b≤1000,n≤a,n≤b,n≤100，矩阵中的所有数都不超过 10^9。
*/

const int N = 1010;
long long arr[N][N];
long long minrow[N][N];
long long maxrow[N][N];
int a, b, n;

void getmin(int row) {
	deque<long long> q;
	for (int i = 1; i <= b; i++) {
		while (!q.empty() && i - q.front() + 1 > n) q.pop_front();
		while (!q.empty() && arr[row][q.back()] >= arr[row][i]) q.pop_back();
		if (q.empty() || arr[row][q.front()] >= arr[row][i]) {
			minrow[row][i] = arr[row][i];
		}
		else {
			minrow[row][i] = arr[row][q.front()];
		}
		q.push_back(i);
	}
}



void getmax(int row) {
	deque<long long> q;
	for (int i = 1; i <= b; i++) {
		while (!q.empty() && i - q.front() + 1 > n) q.pop_front();
		while (!q.empty() && arr[row][q.back()] <= arr[row][i]) q.pop_back();
		if (q.empty() || arr[row][q.front()] <= arr[row][i]) {
			maxrow[row][i] = arr[row][i];
		}
		else {
			maxrow[row][i] = arr[row][q.front()];
		}
		q.push_back(i);
	}
}


void getminCol(int col,int mincol[]) {
	deque<long long> q;
	for (int i = 1; i <= a; i++) {
		while (!q.empty() && i - q.front() + 1 > n) q.pop_front();
		while (!q.empty() && minrow[q.back()][col] >= minrow[i][col]) q.pop_back();
		if (q.empty() || minrow[q.front()][col] >= minrow[i][col]) {
			mincol[i] = minrow[i][col];
		}
		else {
			mincol[i] = minrow[q.front()][col];
		}
		q.push_back(i);
	}


}

void getmaxCol(int col, int maxcol[]) {
	deque<long long> q;
	for (int i = 1; i <= a; i++) {
		while (!q.empty() && i - q.front() + 1 > n) q.pop_front();
		while (!q.empty() && maxrow[q.back()][col] <= maxrow[i][col]) q.pop_back();
		if (q.empty() || maxrow[q.front()][col] <= maxrow[i][col]) {
			maxcol[i] = maxrow[i][col];
		}
		else {
			maxcol[i] = maxrow[q.front()][col];
		}
		q.push_back(i);
	}

}

int main()
{
	cin >> a >> b >> n;

	for (int i = 1; i <= a; i++) {
		for (int j = 1; j <= b; j++) {
			cin >> arr[i][j];
		}
	}

	for (int i = 1; i <= a; i++) {
		getmin(i);
		getmax(i);
	}
	long long ans = 1e18;
	for (int i = n; i <= b; i++) {
		//对每个竖列做滑动窗口 得到最大最小值
		int mincol[N]; int maxcol[N];
		getminCol(i, mincol);
		getmaxCol(i, maxcol);
		for (int j = n; j <= a; j++) {
			ans = min(ans, 1ll * maxcol[j] - mincol[j]);
		}
	}

	cout << ans << endl;
	return 0;
}