matrix searching(二维静态rmq二维线段树实现).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

int t,n,q;
int matrix[310][310];
struct node {
	int l,r;
	node * pl, * pr;
	node * ytree;
	int mmin;
}mem[400000];
int mem_pos;

node *
new_node()
{
	node * pt = &mem[mem_pos ++];
	memset(pt,0,sizeof(pt));
	return pt;
}

node *
make_tree(int x1,int x2,int y1,int y2,bool flag)
{
	node * root = new_node();
	if(flag) {// first dimension
		root ->l = x1;
		root ->r = x2;
		root ->ytree = make_tree(x1,x2,y1,y2,false);
		if(x1 != x2) {
			int mid = (root ->l + root ->r)/2;
			root ->pl = make_tree(x1, mid,y1,y2,true);
			root ->pr = make_tree(mid+1, x2,y1,y2,true);
		}
	}
	else {// second dimension
		root ->l = y1;
		root ->r = y2;
		if(y1 != y2) {
			int mid = (root ->l + root ->r)/2;
			root ->pl = make_tree(x1,x2,y1,mid,false);
			root ->pr = make_tree(x1,x2,mid+1,y2,false);
			root ->mmin = min(root ->pl ->mmin, root ->pr ->mmin);
		}
		else {
			root ->mmin = matrix[x1][y1];
			int i;
			for(i=x1+1;i<=x2;i++) {
				root ->mmin = min(root ->mmin, matrix[i][y1]);
			}
		}
	}
	return root;
}

int
query(node * root, int x1,int x2,int y1,int y2,bool flag)
{
	int t1,t2;
	int mid = (root ->l + root ->r)/2;
	if(flag) {// first dimension
		if(root ->l == x1 && root ->r == x2) {
			return query(root ->ytree, x1,x2,y1,y2,false);
		}
		else {
			if(x2 <= mid) {
				return query(root ->pl,x1,x2,y1,y2,true);
			}
			if(x1 > mid) {
				return query(root ->pr,x1,x2,y1,y2,true);
			}
			t1 = query(root ->pl,x1,mid,y1,y2,true);
			t2 = query(root ->pr,mid+1,x2,y1,y2,true);
		}
	}
	else {// second dimension
		if(root ->l == y1 && root ->r == y2) {
			return root ->mmin;
		}
		else {
			if(y2 <= mid) {
				return query(root ->pl,x1,x2,y1,y2,false);
			}
			if(y1 > mid) {
				return query(root ->pr,x1,x2,y1,y2,false);
			}
			t1 = query(root ->pl,x1,x2,y1,mid,false);
			t2 = query(root ->pr,x1,x2,mid+1,y2,false);
		}
	}
	return min(t1,t2);
}

int main()
{
	int i,j,k;
	int c1,c2,r1,r2;
	scanf("%d",&t);
	while(t --) {
		scanf("%d", &n);
		for(i=1;i<=n;i++) {
			for(j=1;j<=n;j++) {
				scanf("%d", &matrix[i][j]);
			}
		}
		mem_pos = 0;
		node * root = make_tree(1,n,1,n,true);
		scanf("%d", &q);
		while(q --) {
			scanf("%d %d %d %d",&r1,&c1,&r2,&c2);
			printf("%d\n", query(root,r1,r2,c1,c2,true));
		}
	}
}