|
|
題目鏈接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2859
  /**//*
 題意：
給定一個(gè)n*n(n <= 300)的矩陣，然后是(T <= 10^6)次詢問(wèn)，每次詢問(wèn)某個(gè)子矩
陣中的最小值。
解法：
二維線段樹 或者 二維RMQ
思路：
一維線段樹是一顆完全二叉樹，那么二維線段樹無(wú)疑就是一顆完全四叉樹，換言
之，每個(gè)結(jié)點(diǎn)有四個(gè)兒子，這里為了空間不浪費(fèi)，將所有結(jié)點(diǎn)記錄在一個(gè)一維數(shù)組中
，每個(gè)結(jié)點(diǎn)的四個(gè)兒子采用編號(hào)的方式存儲(chǔ)，在建樹之前將每個(gè)結(jié)點(diǎn)的信息全部初始
化，初始化的時(shí)候需要注意的是每次將當(dāng)前結(jié)點(diǎn)的四個(gè)兒子清空，然后判斷它本身是
否是葉子結(jié)點(diǎn)，可以通過(guò)x和y區(qū)間端點(diǎn)是否重合來(lái)判斷，最后再來(lái)生成四個(gè)兒子編號(hào)
，然后往下遞歸，遞歸結(jié)束后根據(jù)四個(gè)兒子的最小值更新當(dāng)前的最小值。再來(lái)看詢問(wèn)
，和一維的情況類似，一維是對(duì)區(qū)間交，而二維則是對(duì)矩形交，如果詢問(wèn)的二維區(qū)間
和當(dāng)前結(jié)點(diǎn)管理的二維區(qū)間沒有交集，顯然不可能有最小值，直接返回inf，否則如果
詢問(wèn)的二維區(qū)間完全包含了當(dāng)前結(jié)點(diǎn)管理的二維區(qū)間，那么返回結(jié)點(diǎn)最小值。否則遞
歸當(dāng)前結(jié)點(diǎn)的四個(gè)兒子，取最小值，回歸到根節(jié)點(diǎn)就得到了詢問(wèn)區(qū)間的最值了。
需要注意的是在建樹的時(shí)候不要在葉子結(jié)點(diǎn)生成多余的兒子結(jié)點(diǎn)，這樣內(nèi)存會(huì)多
一倍，如果開得不夠大有可能下標(biāo)越界，開得太大有可能超內(nèi)存。還有就是在二維線
段樹的結(jié)點(diǎn)上信息會(huì)多了不少，能節(jié)省空間盡量節(jié)省，比如每個(gè)結(jié)點(diǎn)管理的區(qū)間端點(diǎn)
不可能很大，所以不需要int，short就足夠了。
 */
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define maxn 310
#define inf (1<<30)-1
struct Tree  {
int Min; // 當(dāng)前結(jié)點(diǎn)區(qū)間最小值
int son[4]; // 四個(gè)兒子在數(shù)組中的編號(hào)
short x[2], y[2]; // 當(dāng)前結(jié)點(diǎn)管理的二維區(qū)間
}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;
}
|