HDU 1823 Luck and Love 二维线段树

简介:
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


标准二维线段树模板。

代码:

#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,如需转载请自行联系原作者

相关文章
|
6月前
|
Java
hdu-4883- (Best Coder) TIANKENG’s restaurant
hdu-4883- (Best Coder) TIANKENG’s restaurant
26 0
|
12月前
|
机器学习/深度学习
hdu 1061 Rightmost Digit
hdu 1061 Rightmost Digit
28 0
|
测试技术
HDU-1847,Good Luck in CET-4 Everybody!(巴什博弈)
HDU-1847,Good Luck in CET-4 Everybody!(巴什博弈)
|
存储
HDOJ/HDU 2140 Michael Scofield's letter(字符转换~)
HDOJ/HDU 2140 Michael Scofield's letter(字符转换~)
81 0
HDOJ(HDU) 2115 I Love This Game(排序排序、、、)
HDOJ(HDU) 2115 I Love This Game(排序排序、、、)
91 0
|
机器学习/深度学习 网络架构
题解 UVA10212 【The Last Non-zero Digit.】
题目链接 这题在学长讲完之后和看完题解之后才明白函数怎么构造。这题构造一个$f(n)$$f(n)$ $=$ $n$除以 $2^{a}$ $*$ $5^{b}$ ,$a$ , $b$ 分别是 $n$ 质因数分解后$2,5$的个数。
1231 0
|
存储
HDOJ/HDU 2140 Michael Scofield&#39;s letter(字符转换~)
Problem Description I believe many people are the fans of prison break. How clever Michael is!! In order that the message won’t be found b...
937 0
【HDU 5510 Bazinga】字符串
2015沈阳区域赛现场赛第2题 题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5510 题意:给定一个由字符串组成的序列,一共n个元素,每个元素是一个不超过2000个字符的字符串。求"存在秩小于 i 且不是 i 的子串"的最大的 i (1
903 0
|
机器学习/深度学习 Java 网络架构