Problem Description
世界上上最远的距离不是相隔天涯海角
而是我在你面前
可你却不知道我爱你
―― 张小娴
前段日子,枫冰叶子给Wiskey做了个征婚启事。聘礼达到500万哦,天哪,但是天文数字了啊,不知多少MM蜂拥而至。顿时万人空巷,连扫地的大妈都来凑热闹来了。―_―|||
因为人数太多,Wiskey实在忙只是来,就把统计的事情全交给了枫冰叶子。自己跑回家歇息去了。
而是我在你面前
可你却不知道我爱你
―― 张小娴
前段日子,枫冰叶子给Wiskey做了个征婚启事。聘礼达到500万哦,天哪,但是天文数字了啊,不知多少MM蜂拥而至。顿时万人空巷,连扫地的大妈都来凑热闹来了。―_―|||
因为人数太多,Wiskey实在忙只是来,就把统计的事情全交给了枫冰叶子。自己跑回家歇息去了。
这可够枫冰叶子忙的了,他要处理的有两类事情,一是得接受MM的报名,二是要帮Wiskey查找符合要求的MM中缘分最高值。
Input
本题有多个測试数据。第一个数字M,表示接下来有连续的M个操作,当M=0时处理中止。
接下来是一个操作符C。
接下来是一个操作符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。
对查找不到的询问。输出-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
标准二维线段树模板。
。
代码:
#include<iostream> #include<cstdio> #include<cstring> using namespace std; struct node { int la,ra; int max1; //存该段最大值 }; struct node1 { int left,right; node w[4005]; //活泼度乘10整形更好比較 } q[405]; //身高可减100(0~100之间) int num; void sub_build(int la,int ra,int i1,int i) //二维 { q[i].w[i1].la=la; q[i].w[i1].ra=ra; q[i].w[i1].max1=-1; if(la==ra) return; int m=(la+ra)/2; sub_build(la,m,2*i1,i); sub_build(m+1,ra,2*i1+1,i); } void build(int left,int right,int la,int ra,int i) //建树 { q[i].left=left; q[i].right=right; sub_build(la,ra,1,i); if(left==right) return; int m=(left+right)/2; build(left,m,la,ra,2*i); build(m+1,right,la,ra,2*i+1); } void sub_update(int b,int c,int i1,int i) { if(c>q[i].w[i1].max1) { q[i].w[i1].max1=c; } if(q[i].w[i1].la==q[i].w[i1].ra) return; if(b<=q[i].w[2*i1].ra) sub_update(b,c,2*i1,i); else sub_update(b,c,2*i1+1,i); } void update(int a,int b,int c,int i) { sub_update(b,c,1,i); if(q[i].left==q[i].right) { return; } if(a<=q[2*i].right) update(a,b,c,2*i); else update(a,b,c,2*i+1); } int sub_query(int a1,int a2,int i1,int i) { if(q[i].w[i1].la==a1&&q[i].w[i1].ra==a2) { return q[i].w[i1].max1; } if(a2<=q[i].w[2*i1].ra) return sub_query(a1,a2,2*i1,i); else if(a1>=q[i].w[2*i1+1].la) return sub_query(a1,a2,2*i1+1,i); else { return max(sub_query(a1,q[i].w[2*i1].ra,2*i1,i),sub_query(q[i].w[2*i1+1].la,a2,2*i1+1,i)); } } void query(int h1,int h2,int a1,int a2,int i) { if(q[i].left==h1&&q[i].right==h2) { num= max(num,sub_query(a1,a2,1,i)); return; } if(h2<=q[2*i].right) query(h1,h2,a1,a2,2*i); else if(h1>=q[2*i+1].left) query(h1,h2,a1,a2,2*i+1); else { query(h1,q[2*i].right,a1,a2,2*i); query(q[2*i+1].left,h2,a1,a2,2*i+1); } } int main() { int t,m,n,i,j,s,a,a1,bb,cc,bb1; double b,b1,c1,c; char ww; while(scanf("%d",&t)!=EOF) { if(t==0) break;build(0,100,0,1000,1); while(t--) { cin>>ww; if(ww=='I') { scanf("%d%lf%lf",&a,&b,&c); a=a-100; bb=(int)(b*10); cc=(int)(c*10); update(a,bb,cc,1); } else { scanf("%d%d%lf%lf",&a,&a1,&b,&b1); a=a-100; a1=a1-100; if(a>a1) swap(a,a1); bb=(int)(b*10); bb1=(int)(b1*10); if(bb>bb1) swap(bb,bb1); num=-1; query(a,a1,bb,bb1,1); if(num==-1) cout<<-1<<endl; else printf("%.1lf\n",(double)(num*1.0)/10); } } } return 0; }
本文转自mfrbuaa博客园博客,原文链接:http://www.cnblogs.com/mfrbuaa/p/5071366.html,如需转载请自行联系原作者