最大高度差(加强版)
暂无测试数据。
问题描述
我们把一块山地划分为N x N的小块。你已经知道了每一块地的海拔高度。你需要回答若干个询问。一次询问指定了一块S x S的正方形区域(S是一个已经给定的值),你需要回答出在这个区域里最小海拔高度和最大海拔高度相差多少。
输入数据
第一行输入三个用空格隔开的正整数n,s,k,表示山地的大小、一次询问的大小和询问的次数。输入数据保证s<=n。
以下n行为一个N x N的矩阵,该矩阵描述了这个山地的高度情况。这些数字保证是不超过maxint的正整数。
接下来k行每行两个数x,y,询问以第x行第y列的格子作为左上角的S x S的方格中最大的高度差。输入数据保证输入的x,y有意义。
输出数据
对于每一个询问,输出询问的区域中高度差的最大值。
样例输入
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
样例说明
输入数据询问子矩阵:
1 2 6
3 5 2
2 4 6
的最大高度差是多少。
答案为6-1=5。
数据规模
对于100%的数据,n<=2000,k<=10000。
信息
- 难度
- 10
- 分类
- (无)
- 标签
- (无)
- 递交数
- 2
- 已通过
- 0
- 通过率
- 0%
- 上传者