|
|
题目链接：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;
}
|