题意就不赘述了。
二维线段树,第一维是高度,第二维是活泼值, 然后建立树套树。
/*
ID: CUGB-wwj
PROG:
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define INF 2000000000
#define MAXN 105
#define MAXM 1005
#define L(x) x<<1
#define R(x) x<<1|1
#define eps 1e-4
using namespace std;
struct Sub
{
int left, right;
int mx;
int mid(){ return (left + right) >> 1;}
};
struct node
{
int left, right;
Sub subtree[4 * MAXM];
int mid(){ return (left + right) >> 1;}
}tree[4 * MAXN];
void make_subtree(int s, int e, int C, int F)
{
tree[F].subtree[C].left = s;
tree[F].subtree[C].right = e;
tree[F].subtree[C].mx = -1;
if(s == e) return;
int mid = (s + e) >> 1;
make_subtree(s, mid, L(C), F);
make_subtree(mid + 1, e, R(C), F);
}
void make_tree(int s, int e, int C)
{
tree[C].left = s;
tree[C].right = e;
make_subtree(0, 1000, 1, C);
if(s == e) return;
int mid = (s + e) >> 1;
make_tree(s, mid, L(C));
make_tree(mid + 1, e, R(C));
}
void up_sub(int C, int F)
{
tree[F].subtree[C].mx = max(tree[F].subtree[L(C)].mx, tree[F].subtree[R(C)].mx);
}
void update_sub(int p, int v, int C, int F)
{
if(tree[F].subtree[C].left == tree[F].subtree[C].right)
{
tree[F].subtree[C].mx = max(tree[F].subtree[C].mx, v);
return;
}
int mid = tree[F].subtree[C].mid();
if(p <= mid) update_sub(p, v, L(C), F);
else update_sub(p, v, R(C), F);
up_sub(C, F);
}
void update(int pa, int pb, int v, int C)
{
update_sub(pb, v, 1, C);
if(tree[C].left == tree[C].right) return;
int mid = tree[C].mid();
if(pa <= mid) update(pa, pb, v, L(C));
else update(pa, pb, v, R(C));
}
int query_sub(int s, int e, int C, int F)
{
if(tree[F].subtree[C].left >= s && tree[F].subtree[C].right <= e) return tree[F].subtree[C].mx;
int mid = tree[F].subtree[C].mid();
int ret = -1;
if(s <= mid) ret = max(ret, query_sub(s, e, L(C), F));
if(mid < e) ret = max(ret, query_sub(s, e, R(C), F));
return ret;
}
int query(int s, int e, int s2, int e2, int C)
{
if(tree[C].left >= s && tree[C].right <= e) return query_sub(s2, e2, 1, C);
int mid = tree[C].mid();
int ret = -1;
if(s <= mid) ret = max(ret, query(s, e, s2, e2, L(C)));
if(mid < e) ret = max(ret, query(s, e, s2, e2, R(C)));
return ret;
}
int main()
{
int T;
char op[5];
while(scanf("%d", &T) != EOF && T)
{
make_tree(100, 200, 1);
while(T--)
{
scanf("%s", op);
int h1, h2;
double a1, a2, L;
if(op[0] == 'I')
{
scanf("%d%lf%lf", &h1, &a1, &L);
update(h1, (int)(a1 * 10 + eps), (int)(L * 10 + eps), 1);
}
else
{
scanf("%d%d%lf%lf", &h1, &h2, &a1, &a2);
if(h1 > h2) swap(h1, h2);
if(a1 > a2) swap(a1, a2);
int ret = query(h1, h2, (int)(a1 * 10 + eps), (int)(a2 * 10 + eps), 1);
if(ret < 0) puts("-1");
else printf("%.1f\n", ret / 10.0);
}
}
}
return 0;
}
分享到:
相关推荐
hdu 1166线段树代码
hdu 1166线段树
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
【hdu5306】Gorgeous Sequence 线段树区间最值操作-附件资源
线段树入门资料,有利于初学者学习,让他们详细了解线段树。
NULL 博文链接:https://128kj.iteye.com/blog/1738772
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3. hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 ...
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
题面 【题目描述】 有nnn个营地,已知每个营地的人数,有四条命令: (1)Add(1) Add(1)Add iii jjj,iii和jjj为正整数,表示第iii个营地增加jjj个人(jjj不超过303030) (2)Sub(2)Sub(2)Sub iii jjj ,iii和jjj为正...
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。