Description

【题意】
约翰所有的土地被分成 $N \times N$ 块，其中第 $r$ 行第 $c$ 列的玉米质量为 $A_{r,c}$。
经过前期考察，他已经锁定了 $K$ 片区域作为实验基地的候选，其中第 $i$ 片区域是从 $R_i$ 行 $C_i$ 列开始，到 $R_i + B - 1$ 行 $C_i + B - 1$ 列结束的一个 $B \times B$ 的区域。
请帮助约翰计算一下，在这些候选区域里，玉米的最高质量与最低质量之差分别是多少。

【输入格式】
• 第一行三个整数 $N , B , K$($1 \le B \le N \le 250，1 \le K \le 10^5$)。

• 下来 $N \times N$ 的矩阵$A_{i,j}$（ $0 \le A_{i,j} \le 250$）。

• 下来 $K$ 行，每行两个整数 $R_i$ 和 $C_i$（$1 \le R_i, C_i \le N$）。

【输出格式】
• 总共 $K$ 行。第 $i$ 行表示第 $i$ 片候选区域中最高质量与最低质量之差。

【样例输入】
5 3 1
5 1 2 6 3
1 3 5 2 7
7 2 4 6 1
9 9 8 6 5
0 6 9 3 9
1 2

【样例输出】
5

【解释】
最高为 6，最低为 1，所以差是 5

Hint

by hansang:

#include<bits/stdc++.h>
using namespace std;
const int N=260;
int q1[N], q2[N], a[N][N], f1[N][N], f2[N][N]; //1small,2big
int main(){
	int n, m, K; scanf("%d%d%d", &n, &m, &K);
	for(int i=1; i<=n; i++) 
		for(int j=1; j<=n; j++) scanf("%d", &a[i][j]);
	memset(f1, 0x3f, sizeof(f1));
	memset(f2, 0, sizeof(f2));
	for(int i=1; i<=n; i++){
		int l1=1, r1=0, l2=1, r2=0;
		for(int j=1; j<=n; j++){
			int t=max(1, j-m+1);
			while(l1<=r1 && q1[l1]<=j-m) l1++;
			while(l1<=r1 && a[i][q1[r1]]>=a[i][j]) r1--;
			q1[++r1]=j; f1[i][t]=min(f1[i][t], a[i][q1[l1]]);
		while(l2&lt;=r2 &amp;&amp; q2[l2]&lt;=j-m) l2++;
		while(l2&lt;=r2 &amp;&amp; a[i][q2[r2]]&lt;=a[i][j]) r2--;
		q2[++r2]=j; f2[i][t]=max(f2[i][t]&#44; a[i][q2[l2]]);
	}
}
for(int i=1; i&lt;=K; i++){
	int l&#44; r; scanf("%d%d"&#44; &amp;l&#44; &amp;r);
	int s1=N&#44; s2=0;
	for(int j=l; j&lt;=l+m-1; j++){
		s1=min(s1&#44; f1[j][r]);
		s2=max(s2&#44; f2[j][r]);
	}
	printf("%d\n"&#44; s2-s1);
}
return 0;

}

</p>