[ZJU/ZOJ][2859][Matrix Searching][二维fRMQ]

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))

int const N= 302;
int mat[N][N], n, q, pos[N];
int dMin[9][9][N][N];

void initRMQ(){
	int i, j, u, v, a, b, c, d;
	for( pos[0]= -1, i= 1; i<= n; ++i )
	pos[i]= ( ( i& (i- 1) )== 0 )? pos[i- 1]+ 1: pos[i- 1];
	
	for( i= 0; i<= pos[n]; ++i )
	for( j= 0; j<= pos[n]; ++j )
	for( u= 1; u<= n+ 1- (1<<i); u++ )
	for( v= 1; v<= n+ 1- (1<<j); v++ ){
		if( i== 0 && j== 0 ) continue;
		
		if( i== 0 ) dMin[i][j][u][v]= min( dMin[i][j- 1][u][v], dMin[i][j- 1][u][v+ (1<<(j- 1))] );
		else        dMin[i][j][u][v]= min( dMin[i- 1][j][u][v], dMin[i- 1][j][u+ (1<<(i- 1))][v] );
	}
}

int askRMQ( int x1, int y1, int x2, int y2 ){
	int x= pos[x2- x1+ 1], y= pos[y2- y1+ 1];
	
	int a= min( dMin[x][y][x1][y1], dMin[x][y][x2- (1<<x)+ 1][y1] );
	int b= min( dMin[x][y][x1][y2- (1<<y)+ 1], dMin[x][y][x2- (1<<x)+ 1][y2- (1<<y)+ 1] );
	
	return min(a,b);
	
}

int main(){
	int test;
	scanf("%d", &test );
	
	while( test-- ){
		scanf("%d",&n );
		
		for( int i= 1; i<= n; ++i )
		for( int j= 1; j<= n; ++j ){
			scanf("%d",  &mat[i][j] );
			dMin[0][0][i][j]= mat[i][j];
		}
		
		initRMQ();
		scanf("%d", &q );
		int x1, y1, x2, y2;
		for( int i= 0; i< q; ++i ){
			scanf("%d%d%d%d", &x1, &y1, &x2, &y2 );
			
			printf("%d\n", askRMQ( x1, y1, x2, y2 ) );
		}
	}
	
	return 0;
}