Luck and Love(二维线段树)

时间:2023-01-07 06:55:49

Luck and Love

Time Limit: 10000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 54 Accepted Submission(s): 21
 
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
 
Recommend
威士忌
 
/*
题意:略 初步思路:二位线段树,只有一位小数,×10,之后数据就可以用线段树处理 #错误:少了-1的情况,wa到死
*/
#include<bits/stdc++.h>
using namespace std;
int n;
char op[];
int h1,h2,h;
float a,l;
float a1,a2;
/***********************************二维线段树模板(最大值)****************************************/
#define LL long long
#define INF 0x3f3f3f3f
const int N=;
float seg[N][N<<]; // 表示X轴Y轴;
void Build_2(int l,int r,int deep,int rt) // 建y轴方向线段树(二维);
{
seg[deep][rt]=-1.0;
if(l==r) return;
int mid=(l+r)>>;
Build_2(l,mid,deep,rt<<);
Build_2(mid+,r,deep,rt<<|);
}
void Build(int l,int r,int rt) // 建x轴方向线段树(一维);
{
Build_2(,,rt,);
if(l==r) return;
int mid=(l+r)>>;
Build(l,mid,rt<<);
Build(mid+,r,rt<<|);
}
void Insert_2(int act,float love,int l,int r,int deep,int rt) // y轴方向更新数据;(二维)
{
seg[deep][rt]=max(love,seg[deep][rt]);
if(l==r) return;
int mid=(l+r)>>;
if(act<=mid) Insert_2(act,love,l,mid,deep,rt<<);
else Insert_2(act,love,mid+,r,deep,rt<<|);
seg[deep][rt]=max(seg[deep][rt<<],seg[deep][rt<<|]);
}
void Insert(int h,int act,float love,int l,int r,int rt) // x轴,一维;
{
Insert_2(act,love,,,rt,);
if(l==r) return;
int mid=(l+r)>>;
if(h<=mid) Insert(h,act,love,l,mid,rt<<);
else Insert(h,act,love,mid+,r,rt<<|);
}
float Query_2(int L,int R,int l,int r,int rt,int deep) // 查询,y轴,二维;
{
if(L<=l&&R>=r) return seg[deep][rt];
int mid=(l+r)>>;
if(R<=mid) return Query_2(L,R,l,mid,rt<<,deep);
else if(L>mid) return Query_2(L,R,mid+,r,rt<<|,deep);
else return max(Query_2(L,R,l,mid,rt<<,deep),Query_2(L,R,mid+,r,rt<<|,deep));
}
float Query(int h1,int h2,int L,int R,int l,int r,int rt) // x轴,一维;
{
// cout<<h1<<" "<<h2<<" "<<L<<" "<<R<<endl;
if(h1<=l&&h2>=r) return Query_2(L,R,,,,rt);
int mid=(l+r)>>;
if(h2<=mid) return Query(h1,h2,L,R,l,mid,rt<<);
else if(h1>mid) return Query(h1,h2,L,R,mid+,r,rt<<|);
else return max(Query(h1,h2,L,R,l,mid,rt<<),Query(h1,h2,L,R,mid+,r,rt<<|));
}
/***********************************二维线段树模板(最大值)****************************************/
int main(){
// freopen("in.txt","r",stdin);
while(scanf("%d",&n)!=EOF&&n){
Build(,,);
for(int i=;i<n;i++){
scanf("%s",op);
if(op[]=='I'){//插入
scanf("%d%f%f",&h,&a,&l);
// cout<<op[0]<<" "<<h<<" "<<a<<" "<<l<<endl;
int aa=(int)(a*);
// cout<<h<<" "<<aa<<" "<<ll<<endl;
Insert(h,aa,l,,,); }else{//查询
scanf("%d%d%f%f",&h1,&h2,&a1,&a2);
// cout<<op[0]<<" "<<h1<<" "<<h2<<" "<<a1<<" "<<a2<<endl;
if(a1>a2){
float tmp=a1;
a1=a2;
a2=tmp;
}
int A1=(int)(a1*);
int A2=(int)(a2*);
if(h1>h2){
int tmp=h1;
h1=h2;
h2=tmp;
}
// cout<<H1<<" "<<H2<<" "<<A1<<" "<<A2<<endl;
float res=Query(h1,h2,A1,A2,,,);
if(res==-1.0) puts("-1");
else printf("%.1f\n",res);
}
}
}
return ;
}