Luck and Love
Time Limit: 10000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3571 Accepted Submission(s): 901
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）
所有输入的浮点数，均只有一位小数。
接下来是一个操作符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
Author
威士忌
Source
Recommend
威士忌
这个题正解应该是2维线段树，可是我现在还不会，不想直接去看别人的解题报告，就自己想了下，发现要是查询操作的数据不是很多的话用1维线段树+暴力也应该可以水过。
建树的时间复杂度100*1000*log1000
每一次查询的时间复杂度d*log1000，d代表查询的身高区域长度，最大为100
这个题一个比较坑的地方是查询操作的时候
可能 H1 > H2, A1> A2;
Time：437MS（以前WA的时候也是437MS，难道最后一组数据是H1>H2||A1>A2.......） Memory: 2280K
#include<stdio.h>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define max(a,b) a>b?a:b
double node[101][1001<<2];
void build(int tmp,int l,int r,int rt)
{
node[tmp][rt]=-1;
if(l==r)
return ;
int m=(l+r)>>1;
build(tmp,lson);
build(tmp,rson);
}
void update(int tmp,int a,double w,int l,int r,int rt)
{
if(l==r)
{
if(node[tmp][rt]<w)
node[tmp][rt]=w;
return ;
}
int m=(l+r)>>1;
if(a<=m)
update(tmp,a,w,lson);
else
update(tmp,a,w,rson);
node[tmp][rt]=max(node[tmp][rt<<1],node[tmp][rt<<1|1]);
}
double query(int tmp,int L,int R,int l,int r,int rt)
{
if(L<=l && R>=r)
return node[tmp][rt];
if(l==r)
return -1;
int m=(l+r)>>1;
double tmp1=-1,tmp2=-1;
if(L<=m)
tmp1=query(tmp,L,R,lson);
if(R>=m)
tmp2=query(tmp,L,R,rson);
return max(tmp1,tmp2);
}
int main(void)
{
int m,i,j,a,d,tmp1,tmp2,temp0;
double b,c,max,temp1;
char ch[5];
// freopen("d:\\in.txt","r",stdin);
while(scanf("%d",&m),m)
{
for(i=0;i<=100;i++)
{
build(i,0,1000,1);
}
for(i=1;i<=m;i++)
{
scanf("%s",ch);
if(ch[0]=='I')
{
scanf("%d%lf%lf",&a,&b,&c);
d=(int)(b*10);
update(a-100,d,c,0,1000,1);
}
else
{
scanf("%d%d%lf%lf",&a,&d,&b,&c);
if(a>d)
{
temp0=a;
a=d;
d=temp0;
}
if(b>c)
{
temp1=b;
b=c;
c=temp1;
}
tmp1=(int)(b*10);
tmp2=(int)(c*10);
a-=100;
d-=100;
max=-1;
for(j=a;j<=d;j++)
{
b=query(j,tmp1,tmp2,0,1000,1);
if(b>max)
max=b;
}
if(max!=-1)
printf("%.1lf\n",max);
else
printf("-1\n");
}
}
}
return 0;
}
12/9/2 今天看了下用2维线段树的解法，感觉还是不难的，就是写的代码比一维的长了些，开始自己想不看别人的结题报告自己想2维的线段树解法时，思维陷入了一点小误区....所以导致没想出来，看了下别人的的解题报告，理解了后自己写了代码，AC了，时间复杂度下降到原来暴力的1/3以下了，时间上还是有进步的，不过空间上也多用了差不多一倍的内存，我把我参考的那个人的代码也交了一次，结果发现他的代码用的时间和空间都比我大，他的空间比我大我能理解，不过时间比我还慢就让我有点小意外了，他的线段树的代码风格正常情况下应该是时间比我快，空间比我大的.....应该是他没处理好吧...... 这段代码建2维线段树用的时间是100（log100）*1000*log（1000）；（比第一种方法有点暴力的那种时间要长） 不过每一次操作所用的时间都是log100*log1000，比第一种方法时间要小很多，当操作很多是，这个方法在时间上还是有很大的优势的
Time：125MSMemory：4296LK
#include<stdio.h>
#include<iostream>
using namespace std;
#define MAXN1 101
#define MAXN2 1001
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define max(a,b) a>b?a:b
double num[MAXN1<<2][MAXN2<<2];
void build_y(int node,int l,int r,int rt)
{
num[node][rt]=-1;
if(l==r)
return ;
int m=(l+r)>>1;
build_y(node,lson);
build_y(node,rson);
}
void build_x(int l,int r,int rt)
{
build_y(rt,0,1000,1);
if(l==r)
return ;
int m=(l+r)>>1;
build_x(lson);
build_x(rson);
}
void update_y(int node,int f,double luck,int l,int r,int rt)
{
num[node][rt]=max(num[node][rt],luck);
if(l==r)
return ;
int m=(l+r)>>1;
if(f<=m)
update_y(node,f,luck,lson);
else
update_y(node,f,luck,rson);
}
void update_x(int h,int f,double luck,int l,int r,int rt)
{
update_y(rt,f,luck,0,1000,1);
if(l==r)
return ;
int m=(l+r)>>1;
if(h<=m)
update_x(h,f,luck,lson);
else
update_x(h,f,luck,rson);
}
double query_y(int node,int f_l,int f_r,int l,int r,int rt)
{
if(f_l<=l && f_r>=r)
return num[node][rt];
if(l==r)
return -1;
int m=(l+r)>>1;
double tmp1=-1,tmp2=-2;
if(f_l<=m)
tmp1=query_y(node,f_l,f_r,lson);
if(f_r>m)
tmp2=query_y(node,f_l,f_r,rson);
return max(tmp1,tmp2);
}
double query_x(int h_l,int h_r,int f_l,int f_r,int l,int r,int rt)
{
if(h_l<=l && h_r>=r)
return query_y(rt,f_l,f_r,0,1000,1);
if(l==r)
return -1;
int m=(l+r)>>1;
double tmp1=-1,tmp2=-1;
if(h_l<=m)
tmp1=query_x(h_l,h_r,f_l,f_r,lson);
if(h_r>m)
tmp2=query_x(h_l,h_r,f_l,f_r,rson);
return max(tmp1,tmp2);
}
int main(void)
{
int M,h1,h2,i;
double f1,f2,tmp;
char ch[2];
// freopen("d:\\in.txt","r",stdin);
while(scanf("%d",&M),M)
{
build_x(0,100,1);
for(i=1;i<=M;i++)
{
scanf("%s",ch);
if(ch[0]=='I')
{
scanf("%d%lf%lf",&h1,&f1,&f2);
update_x(h1-100,(int)(f1*10),f2,0,100,1);
}
else
{
scanf("%d%d%lf%lf",&h1,&h2,&f1,&f2);
if(h1>h2)
swap(h1,h2);
if(f1>f2)
swap(f1,f2);
tmp=query_x(h1-100,h2-100,(int)(f1*10),(int)(f2*10),0,100,1);
if(tmp<-0.5)
puts("-1");
else
printf("%.1lf\n",tmp);
}
}
}
return 0;
}