luogu2216

题目描述

给定、、，要求所有大小为的正方形内部的最大值和最小值之差的最小值。

解题思路

我们考虑一下怎么求最大值，最小值同理。一个正方形的最大值，即每一行的最大值的最大值。具体到求解每一个正方形每一行的最大值，我们可以使用单调队列来做。每一次从队头删除不在范围内的节点，从队尾添加新节点，并且移除队列中比它小的节点，因为这些节点都比它更先离开队列，且对答案没有贡献。

如此按行做单调队列，再对得到的答案沿着列做单调队列，就可以求得每个正方形的最大值。

给出单调队列的模版：

int q[N], qhead = 0, qtail = 0;
void func() {
	qhead = 1, qtail = 0;
	for (int i = 1; i <= n; ++i) {
		while (qhead <= qtail && check_key(q[qtail])) --qtail;
		q[++qtail] = tmp;
		while (qhead <= qtail && check_bound(q[qhead])) ++qhead;
	}
}