随笔 - 97, 文章 - 22, 评论 - 81, 引用 - 0
数据加载中……

ZJU 2859 Matrix Searching

题目链接: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(
11, 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;
}

posted on 2011-03-30 13:07 英雄哪里出来 阅读(1383) 评论(0)  编辑 收藏 引用 所属分类: 线段树


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理