题目：

Matrix Searching

Given an n*n matrix A, whose entries Ai,j are integer numbers ( 1 <= i <= n, 1 <= j <= n ). An operation FIND the minimun number in a given ssub-matrix.

Input

The first line of the input contains a single integer T , the number of test cases.

For each test case, the first line contains one integer n (1 <= n <= 300), which is the sizes of the matrix, respectively. The next n lines with n integers each gives the elements of
the matrix.

The next line contains a single integer N (1 <= N <= 1,000,000), the number of queries. The next N lines give one query on each line, with four integers r1, c1, r2, c2 (1 <= r1 <= r2
<= n, 1 <= c1 <= c2 <= n), which are the indices of the upper-left corner and lower-right corner of the sub-matrix in question.

Output

For each test case, print N lines with one number on each line, the required minimum integer in the sub-matrix.

Sample Input

1
2
2 -1
2 3
2
1 1 2 2
1 1 2 1

Sample Output

-1
2

题解：

题目显然是RMQ问题，而且是二维的。

大意是讲，给定一个n*n(n <= 300)的矩阵，然后是(T <= 10^6)次询问，每次询问某个子矩阵中的最小值。

想必大家对RMQ问题不是特别陌生，说起来，ST算法的核心就在于“二分”，当然不是传统意义上的二分了，毕竟是二维的，要分类来进行二分处理。

简单地说，定义dp[row][col][i][j] 表示[row,row+2^i-1] x [col,col+2^j-1] 二维区间内的最小值。

那么，有：

dp[row][col][i][j]

= min( [row,row+ 2^(i-1)-1] x [col,col+2^j-1] ,
[row+2^(i-1),row+2^i-1] x [col,col+2^j-1] )

（左半区的最小值 和 右半区的最小值）

= min( dp[row][col][i-1][j] , dp[row + (1<<(i-1))][col][i-1][j] )

（左半区的最小值 和 右半区的最小值，相当于固定了y轴坐标不变，将区域分割成左右两个区）

同样的，也有：

dp[row][col][i][j]=

= min( [row,row+ 2^i-1] x [col,col+2^(j-1)-1] ,
[row,row+2^i-1] x [col+2^(i-1),col+2^j-1]
)

（上半区的最小值 和 下半区的最小值）

= min( dp[row][col][i][j-1] ,
dp[row][col + (1<<(i-1))][i][j-1] ) 

（上半区的最小值 和 下半区的最小值，相当于固定了x轴坐标不变，将区域分割成上下两个区）

时间复杂度是O(N * M * log N * log M)

空间复杂度是O(N * M * log N * log M)

已经非常的高效了。

代码示例：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int maxn = 310;

int N;
int val[maxn][maxn];

//2D RMQ
//dp[row][col][i][j] 表示[row,row+2^i-1]x[col,col+2^j-1] 二维区间内的最小值.
//dp[row][col][i][j] = 
//	min( dp[row][col][i-1][j], dp[row + (1<<(i-1))][col][i-1][j] )
//    	min( dp[row][col][i][j-1], dp[row][col + (1<<(j-1))][i][j-1] )

int code(int i){
    return log(double(i)) / log(2.0);
}

int dp[maxn][maxn][9][9];
void initRMQ(int N,int M){
	for (int row=1;row<=N;row++){
	for (int col=1;col<=M;col++){
		dp[row][col][0][0]=val[row][col];
	}
	}
	int n = code(N);
	int m = code(M);
	for (int i=0;i<=n;i++){
	for (int j=0;j<=m;j++){
		if(i == 0 && j==0)continue;
		for (int row=1;row+(1<<i)-1<=N;row++){
		for (int col=1;col+(1<<j)-1<=M;col++){
			if (i==0){//水平划分
				dp[row][col][i][j] = min(dp[row][col][i][j-1] , dp[row][col+(1<<(j-1))][i][j-1]);
			}
			else {//竖直划分
				dp[row][col][i][j] = min(dp[row][col][i-1][j] , dp[row+(1<<(i-1))][col][i-1][j]);
			}
		}
		}
	}
	}
}

int RMQ(int x1,int x2,int y1,int y2){
	int kx = code(x2-x1+1);
	int ky = code(y2-y1+1);
	int m1 = dp[x1][y1][kx][ky];
	int m2 = dp[x2-(1<<kx)+1][y1][kx][ky];
	int m3 = dp[x1][y2-(1<<ky)+1][kx][ky];
	int m4 = dp[x2-(1<<kx)+1][y2-(1<<ky)+1][kx][ky];
	return min( min(m1,m2), min(m3,m4) );
}


int main(){
	int T;
	int M;
	int x1,y1,x2,y2;
	scanf("%d",&T);
	while(T--){
		scanf("%d",&N);
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=N; j++) {
				scanf("%d",&val[i][j]);
			}
		}
		initRMQ(N,N);
		scanf("%d",&M);
		while(M--)	{
			scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
			printf("%d\n",RMQ(x1,x2,y1,y2));
		}
	}
	return 0;
}