站外二维 RMQ 求条

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=305;
int n,m,q;
int lg[N];
int st[10][10][N][N]; 
int main()
{
	lg[1]=0;
	for(int i=2;i<=300;i++)
		lg[i]=lg[i>>1]+1;	
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&st[0][0][i][j]);
	//处理1*2^kj 
	for(int kj=1;kj<=lg[m];kj++)
		for(int i=1;i<=n;i++)
			for(int j=1;j+(1<<kj)-1<=m;j++)
				st[0][kj][i][j]=max(st[0][kj-1][i][j],st[0][kj-1][i][j+(1<<kj-1)]);
	//处理2^ki*1
	for(int ki=1;ki<=lg[n];ki++)
		for(int i=1;i+(1<<ki)-1<=n;i++)
			for(int j=1;j<=m;j++)
				st[ki][0][i][j]=max(st[ki-1][0][i][j],st[ki-1][0][i+(1<<ki-1)][j]);
	//处理正常情况
	for(int ki=1;ki<=lg[n];ki++)
		for(int kj=1;kj<=lg[m];kj++)
			for(int i=1;i+(1<<ki)-1<=n;i++)
				for(int j=1;j+(1<<kj)-1<=m;j++)
					st[ki][kj][i][j]=max({st[ki-1][kj-1][i][j],st[ki-1][kj-1][i+(1<<ki-1)][j],st[ki-1][kj-1][i][j+(1<<kj-1)],st[ki-1][kj-1][i+(1<<ki-1)][j+(1<<kj-1)]});
	scanf("%d",&q);
	while(q--)
	{
		int x1,y1,x2,y2;
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		int ki=lg[x2-x1+1],kj=lg[y2-y1+1];
		int maxn=max({st[ki][kj][x1][y1],st[ki][kj][x2-(1<<ki)+1][y1],st[ki][kj][x1][y2-(1<<kj)+1],st[ki][kj][x2-(1<<ki)+1][y2-(1<<kj)+1]});
		printf("%d %s\n",maxn,max({st[0][0][x1][y1],st[0][0][x1][y2],st[0][0][x2][y1],st[0][0][x2][y2]})==maxn?"yes":"no");
	}	
	return 0;
}