|
|
題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=1823
  /**//*
 題意：
二維區間求最大值。
解法：
二維線段樹 或者 二維RMQ
思路：
一維線段樹是一顆完全二叉樹，那么二維線段樹無疑就是一顆完全四叉樹，換言
之，每個結點有四個兒子，這里為了空間不浪費，將所有結點記錄在一個一維數組中
，每個結點的四個兒子采用編號的方式存儲，在建樹之前將每個結點的信息全部初始
化，初始化的時候需要注意的是每次將當前結點的四個兒子清空，然后判斷它本身是
否是葉子結點，可以通過x和y區間端點是否重合來判斷，最后再來生成四個兒子編號
，然后往下遞歸，遞歸結束后根據四個兒子的最小值更新當前的最小值。再來看詢問
，和一維的情況類似，一維是對區間交，而二維則是對矩形交，如果詢問的二維區間
和當前結點管理的二維區間沒有交集，顯然不可能有最小值，直接返回inf，否則如果
詢問的二維區間完全包含了當前結點管理的二維區間，那么返回結點最小值。否則遞
歸當前結點的四個兒子，取最小值，回歸到根節點就得到了詢問區間的最值了。
需要注意的是在建樹的時候不要在葉子結點生成多余的兒子結點，這樣內存會多
一倍，如果開得不夠大有可能下標越界，開得太大有可能超內存。還有就是在二維線
段樹的結點上信息會多了不少，能節省空間盡量節省，比如每個結點管理的區間端點
不可能很大，所以不需要int，short就足夠了。
 */
 #include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
#define maxn 200010
#define eps 1e-6
typedef double Type;
Type bin[maxn];
int size, tot;
int B(Type val)  {
int l = 0;
int r = tot-1;
  while(l <= r) {
int m = (l + r) >> 1;
if(fabs(bin[m] - val) < eps)
return m;
if(val > bin[m]) {
l = m + 1;
 }else
r = m - 1;
}
}
struct Op {
int mode;
Type HH, AA, L;
Type H[2], A[2];
void SCANF(int _mode) {
mode = _mode;
if(mode == 0) {
// 插入操作
scanf("%lf %lf %lf", &HH, &AA, &L);
bin[size++] = HH;
bin[size++] = AA;
}else {
// 詢問操作
scanf("%lf %lf %lf %lf", &H[0], &H[1], &A[0], &A[1]);
for(int i = 0; i < 2; i++) {
bin[size++] = H[i];
bin[size++] = A[i];
}
if(H[0] > H[1]) swap(H[0], H[1]);
if(A[0] > A[1]) swap(A[0], A[1]);
}
}
}O[maxn];
struct Tree {
int son[4];
Type Max;
void clear() {
Max = -1;
for(int i = 0; i < 4; i++)
son[i] = -1;
}
}T[maxn*4];
int all;
Type MMax(Type a, Type b) {
return a > b ? a : b;
}
void Insert(int& root, int x, int y, int lx, int rx, int ly, int ry, Type Max) {
if(x > rx || x < lx || y > ry || y < ly)
return ;
if(root == -1) {
root = all++;
T[root].clear();
}
T[root].Max = MMax(T[root].Max, Max);
if(lx == rx && ly == ry)
return ;
int midx0 = (lx + rx) >> 1;
int midy0 = (ly + ry) >> 1;
int midx1 = (lx==rx) ? midx0 : midx0 + 1;
int midy1 = (ly==ry) ? midy0 : midy0 + 1;
Insert(T[root].son[0], x, y, lx, midx0, ly, midy0, Max);
Insert(T[root].son[1], x, y, lx, midx0, midy1, ry, Max);
Insert(T[root].son[2], x, y, midx1, rx, ly, midy0, Max);
Insert(T[root].son[3], x, y, midx1, rx, midy1, ry, Max);
}
void Query(int root, int x0, int x1, int y0, int y1,
int lx, int rx, int ly, int ry, Type& Max) {
if(x0 > rx || x1 < lx || y0 > ry || y1 < ly || root == -1 || T[root].Max <= Max)
return ;
if(x0 <= lx && rx <= x1 && y0 <= ly && ry <= y1) {
Max = MMax(Max, T[root].Max);
return ;
}
int midx0 = (lx + rx) >> 1;
int midy0 = (ly + ry) >> 1;
int midx1 = (lx==rx) ? midx0 : midx0 + 1;
int midy1 = (ly==ry) ? midy0 : midy0 + 1;
Query(T[root].son[0], x0, x1, y0, y1, lx, midx0, ly, midy0, Max);
Query(T[root].son[1], x0, x1, y0, y1, lx, midx0, midy1, ry, Max);
Query(T[root].son[2], x0, x1, y0, y1, midx1, rx, ly, midy0, Max);
Query(T[root].son[3], x0, x1, y0, y1, midx1, rx, midy1, ry, Max);
}
int n;
int main() {
int i;
char str[10];
while(scanf("%d", &n) != EOF && n) {
size = 0;
all = 0;
for(i = 0; i < n; i++) {
scanf("%s", str);
if(!strcmp(str, "I")) {
O[i].SCANF(0);
}else {
O[i].SCANF(1);
}
}
sort(bin, bin + size);
tot = 0;
for(i = 0; i < size; i++) {
if(!i || fabs(bin[i] - bin[i-1]) > eps) {
bin[tot++] = bin[i];
}
}
int root = -1;
for(i = 0; i < n; i++) {
if(O[i].mode == 0) {
Insert(root, B(O[i].HH), B(O[i].AA), 0, tot - 1, 0, tot - 1, O[i].L);
}else {
Type ans = -1;
Query(root, B(O[i].H[0]), B(O[i].H[1]), B(O[i].A[0]), B(O[i].A[1]), 0, tot - 1, 0, tot - 1, ans);
if(ans < 0) {
printf("-1\n");
}else
printf("%.1lf\n", ans);
}
}
}
return 0;
}
|