题目描述

小A约一些朋友去露营，到了晚上他们决定各自选择较为平坦的一块地去搭建帐篷，小A有一张旅游景点的地图，地图的大小为 $N \times N$ $（1 \le N \le 250）$ 单位的矩形区域。每个单位都有标识了用整数表示的海拔高度 $（0 \le 海拔 \le 250）$。

现在小A有 $K$ 个朋友 $（1 \le K \le 1 \times 10^5）$ 需要询问某个大小为 $B \times B$ 区域是否适合搭建帐篷，对于每次询问都要给出相应 $B \times B$ 区域内海拔的高度差。

输入

第一行有三个整数：$N, B, K$，如问题描述所述意义。

接下来 $N$ 行，每行包含 $N$ 个以空格分隔的整数。每个整数表示相应位置的海拔高度。

再接下来 $K$ 行，每行包含两个空格分隔的整数。表示需要查询的 $B \times B$ 区域的左上角。整数在$[1,N-B+1]$范围内。

输出

$K$ 行每行一个整数，表示每个查询中的最大值和最小值之间的差。

0分代码

#include<bits/stdc++.h>
using namespace std;
const int maxN=259;
int fi[maxN][maxN][8][8],fa[maxN][maxN][8][8];//两个数组记录范围内的最小海拔和最大海拔，四个维度分别表示：矩阵左上方的横坐标、纵坐标，以及倍增的数
int n,m,p;
void init(){
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			cin>>fi[i][j][0][0];
			fa[i][j][0][0]=fi[i][j][0][0];
		}
	}
   
	for (int len=1;(1<<len)<=n;len++){
		for (int k=1;(1<<k)<=n;k++){
			for (int i=1;i+(1<<len)-1<=n;i++){
				for (int j=1;j+(1<<len)-1<=n;j++){
					fa[i][j][len][k]=max(max(fa[i][j][len-1][k],fa[i+(1<<len-1)][j][len-1][k]),max(fa[i][j][len][k-1],fa[i+(1<<len-1)][j+(1<<k-1)][len][k-1]));
				}
			}
		}
	}
	for (int len=1;(1<<len)<=n;len++){
		for (int k=1;(1<<k)<=n;k++){
			for (int i=1;i+(1<<len)-1<=n;i++){
				for (int j=1;j+(1<<len)-1<=n;j++){
					fi[i][j][len][k]=min(min(fi[i][j][len-1][k],fi[i+(1<<len-1)][j][len-1][k]),min(fi[i][j][len][k-1],fi[i+(1<<len-1)][j+(1<<k-1)][len][k-1]));
				}
			}
		}
	}
   //我觉得应该是上面两个循环出了问题（
}//初始化
int querya(int x,int y,int len){
	int k=0;
	for (;;k++){
		if ((1<<k+1)>len) break;
	}
	int x1=x+len-1,y1=y+len-1;
	return max(max(fa[x][y][k][k],fa[x1-(1<<k)+1][y][k][k]),max(fa[x][y1-(1<<k)+1][k][k],fa[x1-(1<<k)+1][y1-(1<<k)+1][k][k]));
}//查询范围内海拔最大值
int queryi(int x,int y,int len){
	int k=0;
	for (;;k++){
		if ((1<<k+1)>len) break;
	}
	int x1=x+len-1,y1=y+len-1;
	return min(min(fi[x][y][k][k],fi[x1-(1<<k)+1][y][k][k]),min(fi[x][y1-(1<<k)+1][k][k],fi[x1-(1<<k)+1][y1-(1<<k)+1][k][k]));
}//查询范围内海拔最小值
int main(){
	cin>>n>>p>>m;
	init();
	for (int i=1;i<=m;i++){
		int a,b;
		cin>>a>>b;
		cout<<querya(a,b,p)-queryi(a,b,p)<<endl;
	}
	return 0;
}

感谢帮助！