首页 > 代码库 > HDU1832 二维线段树求最值(模板)
HDU1832 二维线段树求最值(模板)
Luck and Love |
Time Limit: 10000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) |
Total Submission(s): 50 Accepted Submission(s): 20 |
Problem Description
世界上上最远的距离不是相隔天涯海角
而是我在你面前 可你却不知道我爱你 ―― 张小娴 前段日子,枫冰叶子给Wiskey做了个征婚启事,聘礼达到500万哦,天哪,可是天文数字了啊,不知多少MM蜂拥而至,顿时万人空巷,连扫地的大妈都来凑热闹来了。―_―||| 由于人数太多,Wiskey实在忙不过来,就把统计的事情全交给了枫冰叶子,自己跑回家休息去了。这可够枫冰叶子忙的了,他要处理的有两类事情,一是得接受MM的报名,二是要帮Wiskey查找符合要求的MM中缘分最高值。 |
Input
本题有多个测试数据,第一个数字M,表示接下来有连续的M个操作,当M=0时处理中止。
接下来是一个操作符C。 当操作符为‘I’时,表示有一个MM报名,后面接着一个整数,H表示身高,两个浮点数,A表示活泼度,L表示缘分值。 (100<=H<=200, 0.0<=A,L<=100.0) 当操作符为‘Q’时,后面接着四个浮点数,H1,H2表示身高区间,A1,A2表示活泼度区间,输出符合身高和活泼度要求的MM中的缘分最高值。 (100<=H1,H2<=200, 0.0<=A1,A2<=100.0) 所有输入的浮点数,均只有一位小数。 |
Output
对于每一次询问操作,在一行里面输出缘分最高值,保留一位小数。
对查找不到的询问,输出-1。 |
Sample Input
8 I 160 50.5 60.0 I 165 30.0 80.5 I 166 10.0 50.0 I 170 80.5 77.5 Q 150 166 10.0 60.0 Q 166 177 10.0 50.0 I 166 40.0 99.9 Q 166 177 10.0 50.0 0 |
Sample Output
80.5 50.0 99.9 |
Author
威士忌
|
Source
HDOJ 2007 Summer Exercise(3)- Hold by Wiskey
|
代码:
//二维线段树模板,身高一维,欢乐度二维。 #include<iostream> #include<cstdio> #include<cmath> using namespace std; const int maxn=1003; struct sub_tree{ int l,r,ans; int mid(){return (l+r)>>1;} }; struct tree{ int l,r; int mid(){return (l+r)>>1;} sub_tree st[4*maxn]; }tr[4*maxn]; void build_subtree(int l,int r,int i,int fa){ tr[fa].st[i].l=l; tr[fa].st[i].r=r; tr[fa].st[i].ans=-1; if(l==r) return; int m=(l+r)>>1; build_subtree(l,m,i<<1,fa); build_subtree(m+1,r,i<<1|1,fa); } void build(int l,int r,int i){ tr[i].l=l;tr[i].r=r; build_subtree(0,1000,1,i); if(l==r) return; int m=(l+r)>>1; build(l,m,i<<1); build(m+1,r,i<<1|1); } void up(int i,int fa){ tr[fa].st[i].ans=max(tr[fa].st[i<<1].ans,tr[fa].st[i<<1|1].ans); } void update_subtree(int a,int l,int i,int fa){ if(tr[fa].st[i].l==tr[fa].st[i].r){ tr[fa].st[i].ans=max(tr[fa].st[i].ans,l); return; } int m=tr[fa].st[i].mid(); if(a<=m) update_subtree(a,l,i<<1,fa); else update_subtree(a,l,i<<1|1,fa); up(i,fa); } void update(int h,int a,int l,int i){ update_subtree(a,l,1,i); if(tr[i].l==tr[i].r) return; int m=tr[i].mid(); if(h<=m) update(h,a,l,i<<1); else update(h,a,l,i<<1|1); } int query_subtree(int a1,int a2,int i,int fa){ if(tr[fa].st[i].l>=a1&&tr[fa].st[i].r<=a2) return tr[fa].st[i].ans; int m=tr[fa].st[i].mid(); int Max=-1; if(a1<=m) Max=max(Max,query_subtree(a1,a2,i<<1,fa)); if(a2>m) Max=max(Max,query_subtree(a1,a2,i<<1|1,fa)); return Max; } int query(int h1,int h2,int a1,int a2,int i){ if(tr[i].l>=h1&&tr[i].r<=h2) return query_subtree(a1,a2,1,i); int m=tr[i].mid(); int Max=-1; if(h1<=m) Max=max(Max,query(h1,h2,a1,a2,i<<1)); if(h2>m) Max=max(Max,query(h1,h2,a1,a2,i<<1|1)); return Max; } int main() { int t,h1,h2; double a1,a2,c; char ch[3]; while(scanf("%d",&t)&&t){ build(100,200,1); while(t--){ scanf("%s",ch); if(ch[0]==‘I‘){ scanf("%d%lf%lf",&h1,&a1,&c); update(h1,a1*10,c*10,1); } else{ scanf("%d%d%lf%lf",&h1,&h2,&a1,&a2); if(h1>h2) swap(h1,h2); if(a1>a2) swap(a1,a2); int ans=query(h1,h2,a1*10,a2*10,1); if(ans<0) printf("-1\n"); else printf("%.1lf\n",(double)ans/10.0); } } } return 0; }
HDU1832 二维线段树求最值(模板)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。