|
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1823
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) /**//*
题意:
二维区间求最大值。
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
解法:
二维线段树 或者 二维RMQ
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
思路:
一维线段树是一颗完全二叉树,那么二维线段树无疑就是一颗完全四叉树,换言
之,每个结点有四个儿子,这里为了空间不浪费,将所有结点记录在一个一维数组中
,每个结点的四个儿子采用编号的方式存储,在建树之前将每个结点的信息全部初始
化,初始化的时候需要注意的是每次将当前结点的四个儿子清空,然后判断它本身是
否是叶子结点,可以通过x和y区间端点是否重合来判断,最后再来生成四个儿子编号
,然后往下递归,递归结束后根据四个儿子的最小值更新当前的最小值。再来看询问
,和一维的情况类似,一维是对区间交,而二维则是对矩形交,如果询问的二维区间
和当前结点管理的二维区间没有交集,显然不可能有最小值,直接返回inf,否则如果
询问的二维区间完全包含了当前结点管理的二维区间,那么返回结点最小值。否则递
归当前结点的四个儿子,取最小值,回归到根节点就得到了询问区间的最值了。
需要注意的是在建树的时候不要在叶子结点生成多余的儿子结点,这样内存会多
一倍,如果开得不够大有可能下标越界,开得太大有可能超内存。还有就是在二维线
段树的结点上信息会多了不少,能节省空间尽量节省,比如每个结点管理的区间端点
不可能很大,所以不需要int,short就足够了。
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
*/
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#define maxn 200010
#define eps 1e-6
typedef double Type;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
Type bin[maxn];
int size, tot;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int B(Type val) {
int l = 0;
int r = tot-1;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(l <= r) {
int m = (l + r) >> 1;
if(fabs(bin[m] - val) < eps)
return m;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(val > bin[m]) {
l = m + 1;
}else
r = m - 1;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) struct Op {
int mode;
Type HH, AA, L;
Type H[2], A[2];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) void SCANF(int _mode) {
mode = _mode;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(mode == 0) {
// 插入操作
scanf("%lf %lf %lf", &HH, &AA, &L);
bin[size++] = HH;
bin[size++] = AA;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) }else {
// 询问操作
scanf("%lf %lf %lf %lf", &H[0], &H[1], &A[0], &A[1]);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) 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];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) struct Tree {
int son[4];
Type Max;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) void clear() {
Max = -1;
for(int i = 0; i < 4; i++)
son[i] = -1;
}
}T[maxn*4];
int all;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) Type MMax(Type a, Type b) {
return a > b ? a : b;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) 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 ;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(root == -1) {
root = all++;
T[root].clear();
}
T[root].Max = MMax(T[root].Max, Max);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(lx == rx && ly == ry)
return ;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int midx0 = (lx + rx) >> 1;
int midy0 = (ly + ry) >> 1;
int midx1 = (lx==rx) ? midx0 : midx0 + 1;
int midy1 = (ly==ry) ? midy0 : midy0 + 1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
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);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void Query(int root, int x0, int x1, int y0, int y1,
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) 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 ;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(x0 <= lx && rx <= x1 && y0 <= ly && ry <= y1) {
Max = MMax(Max, T[root].Max);
return ;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
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);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int n;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int main() {
int i;
char str[10];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(scanf("%d", &n) != EOF && n) {
size = 0;
all = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i = 0; i < n; i++) {
scanf("%s", str);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(!strcmp(str, "I")) {
O[i].SCANF(0);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) }else {
O[i].SCANF(1);
}
}
sort(bin, bin + size);
tot = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i = 0; i < size; i++) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(!i || fabs(bin[i] - bin[i-1]) > eps) {
bin[tot++] = bin[i];
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int root = -1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i = 0; i < n; i++) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(O[i].mode == 0) {
Insert(root, B(O[i].HH), B(O[i].AA), 0, tot - 1, 0, tot - 1, O[i].L);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) }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);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(ans < 0) {
printf("-1\n");
}else
printf("%.1lf\n", ans);
}
}
}
return 0;
}
|