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

Source: ZOJ Monthly, June 2007

帮学妹找了一晚上的bug。，，各种调试，。各种报错，。感觉自己水爆了，，赶紧水道高级点的水题压压惊~~

ac代码

#include<stdio.h>

#include<string.h>

#include<math.h>

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

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

int map[301][301];

int minv[301][301][9][9];

int mm[306];

int n,m;

void initrmq()

{

	int i,j;

	for(i=1;i<=n;i++)

	{

		for(j=1;j<=n;j++)

		{

			minv[i][j][0][0]=map[i][j];

		}

	}

	int ii,jj;

	for(ii=0;ii<=mm[n];ii++)

		for(jj=0;jj<=mm[n];jj++)

		{

			if(ii+jj)

			{

				for(i=1;i+(1<<ii)-1<=n;i++)

					for(j=1;j+(1<<jj)-1<=n;j++)

					{

						if(ii)

							minv[i][j][ii][jj]=min(minv[i][j][ii-1][jj],minv[i+(1<<(ii-1))][j][ii-1][jj]);

						else

							minv[i][j][ii][jj]=min(minv[i][j][ii][jj-1],minv[i][j+(1<<(jj-1))][ii][jj-1]);

					}

			}

		}

}

int q_min(int x1,int y1,int x2,int y2)

{

	int k1=mm[x2-x1+1];

	int k2=mm[y2-y1+1];

	x2=x2-(1<<k1)+1;

	y2=y2-(1<<k2)+1;

	return min(min(minv[x1][y1][k1][k2],minv[x1][y2][k1][k2]),min(minv[x2][y1][k1][k2],minv[x2][y2][k1][k2]));

}

void init()

{

	mm[0]=-1;

	int i;

  for(i = 1;i <= 305;i++)

        mm[i] = ((i&(i-1))==0)?mm[i-1]+1:mm[i-1];  

}

int main()

{

	int t;

	init();

	scanf("%d",&t);

	while(t--)

	{

		//int n,m;

		scanf("%d",&n);

		int i,j;

		for(i=1;i<=n;i++)

		{

			for(j=1;j<=n;j++)

				scanf("%d",&map[i][j]);

		}

		initrmq();

		scanf("%d",&m);

		while(m--)

		{

			int r1,c1,r2,c2;

			scanf("%d%d%d%d",&r1,&c1,&r2,&c2);

			printf("%d\n",q_min(r1,c1,r2,c2));

		}

	}

}