|
|
题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2859
  /**//*
 题意：
给定一个n*n(n <= 300)的矩阵，然后是(T <= 10^6)次询问，每次询问某个子矩
阵中的最小值。
解法：
二维线段树 或者 二维RMQ
思路：
一维线段树是一颗完全二叉树，那么二维线段树无疑就是一颗完全四叉树，换言
之，每个结点有四个儿子，这里为了空间不浪费，将所有结点记录在一个一维数组中
，每个结点的四个儿子采用编号的方式存储，在建树之前将每个结点的信息全部初始
化，初始化的时候需要注意的是每次将当前结点的四个儿子清空，然后判断它本身是
否是叶子结点，可以通过x和y区间端点是否重合来判断，最后再来生成四个儿子编号
，然后往下递归，递归结束后根据四个儿子的最小值更新当前的最小值。再来看询问
，和一维的情况类似，一维是对区间交，而二维则是对矩形交，如果询问的二维区间
和当前结点管理的二维区间没有交集，显然不可能有最小值，直接返回inf，否则如果
询问的二维区间完全包含了当前结点管理的二维区间，那么返回结点最小值。否则递
归当前结点的四个儿子，取最小值，回归到根节点就得到了询问区间的最值了。
需要注意的是在建树的时候不要在叶子结点生成多余的儿子结点，这样内存会多
一倍，如果开得不够大有可能下标越界，开得太大有可能超内存。还有就是在二维线
段树的结点上信息会多了不少，能节省空间尽量节省，比如每个结点管理的区间端点
不可能很大，所以不需要int，short就足够了。
 */
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define maxn 310
#define inf (1<<30)-1
struct Tree  {
int Min; // 当前结点区间最小值
int son[4]; // 四个儿子在数组中的编号
short x[2], y[2]; // 当前结点管理的二维区间
}T[maxn*maxn*5];
int Tree_Id;
int n;
int mat[maxn][maxn];
void Build(int fat, int x0, int x1, int y0, int y1) {
int i;
  for(i = 0; i < 4; i++) {
T[fat].son[i] = 0;
 }
T[fat].x[0] = x0; T[fat].x[1] = x1;
T[fat].y[0] = y0; T[fat].y[1] = y1;
if(x0 == x1 && y0 == y1) {
T[fat].Min = mat[x0][y0];
return ;
}
for(i = 0; i < 4; i++) {
T[fat].son[i] = Tree_Id++;
}
int xmid = (x0 + x1) >> 1;
int ymid = (y0 + y1) >> 1;
Build(T[fat].son[0], x0, xmid, y0, ymid);
Build(T[fat].son[1], x0, xmid, (ymid<y1) ? ymid+1 : ymid, y1);
Build(T[fat].son[2], (xmid<x1) ? xmid+1 : xmid, x1, y0, ymid);
Build(T[fat].son[3], (xmid<x1) ? xmid+1 : xmid, x1, (ymid<y1) ? ymid+1 : ymid, y1);
T[fat].Min = T[T[fat].son[0]].Min;
for(i = 1; i < 4; i++) {
if(T[T[fat].son[i]].Min < T[fat].Min)
T[fat].Min = T[T[fat].son[i]].Min;
}
}
int Query(int fat, int x0, int x1, int y0, int y1) {
if(x0 > T[fat].x[1] || x1 < T[fat].x[0]
|| y0 > T[fat].y[1] || y1 < T[fat].y[0]) {
return inf;
}
if(x0 <= T[fat].x[0] && T[fat].x[1] <= x1
&& y0 <= T[fat].y[0] && T[fat].y[1] <= y1) {
return T[fat].Min;
}
int i;
int Min = inf;
for(i = 0; i < 4; i++) {
int v = Query(T[fat].son[i], x0, x1, y0, y1);
if(v < Min)
Min = v;
}
return Min;
}
int main() {
int t;
int i, j;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
Tree_Id = 0;
for(i = 1; i <= n; i++) {
for(j = 1; j <= n; j++) {
scanf("%d", &mat[i][j]);
}
}
Tree_Id = 2;
Build(1, 1, n, 1, n);
int m;
scanf("%d", &m);
while(m--) {
int r[2], c[2];
scanf("%d %d %d %d", &r[0], &c[0], &r[1], &c[1]);
printf("%d\n", Query(1, r[0], r[1], c[0], c[1]));
}
}
return 0;
}
|