首页 > ACM题库 > HDU-杭电 > HDU 1823 Luck and Love-线段树-[解题报告] C++
2013
12-23

HDU 1823 Luck and Love-线段树-[解题报告] C++

Luck and Love

问题描述 :

世界上上最远的距离不是相隔天涯海角
而是我在你面前
可你却不知道我爱你
                �� 张小娴

前段日子,枫冰叶子给Wiskey做了个征婚启事,聘礼达到500万哦,天哪,可是天文数字了啊,不知多少MM蜂拥而至,顿时万人空巷,连扫地的大妈都来凑热闹来了。�_�|||
由于人数太多,Wiskey实在忙不过来,就把统计的事情全交给了枫冰叶子,自己跑回家休息去了。这可够枫冰叶子忙的了,他要处理的有两类事情,一是得接受MM的报名,二是要帮Wiskey查找符合要求的MM中缘分最高值。

输入:

本题有多个测试数据,第一个数字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)
所有输入的浮点数,均只有一位小数。

输出:

对于每一次询问操作,在一行里面输出缘分最高值,保留一位小数。
对查找不到的询问,输出-1。

样例输入:

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

样例输出:

80.5
50.0
99.9

继续二维线段树。

这题坑姐啊!!!调了一晚上啊啊啊!!!

不过也更理解二维线段树的更新过程了。我开始弄的二维的更新的可能更新到没有包含更新区间,也给更新了,昨晚躺在床上才想到T T。。。后来发现,又少写个等号,今早改后AC。很纠结啊,这个东西。

想清楚了,刚把代码改得更简洁了点,因为这个是点树啊,而我是用线段树模拟的,需要保证每次更新的一定是更新区间的父区间。= =。。。

#include <queue>
#include <stack>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <limits.h>
#include <string.h>
#include <string>
#include <algorithm>
#define MID(x,y) ( ( x + y ) >> 1 )
#define L(x) ( x << 1 )
#define R(x) ( x << 1 | 1 )
#define BUG puts("here!!!")

using namespace std;

const int MAX = 110;
const int MAXM = 1005;
const int inf = 10000000;
struct Tnode{
    int l,r,val;
    int getlen() { return r - l;}
    int getmid() { return MID(l,r);}
    void lr(int ll,int rr){ l = ll; r = rr;}
};
struct T2node
{ 
    int l,r;
    Tnode son[MAXM<<2];
    int getlen() { return r - l;}
    int getmid() { return MID(l,r);}
    void lr(int ll,int rr){ l = ll; r = rr;}
    
};
T2node node[MAX<<2];
void init()
{
    memset(node,0,sizeof(node));
}
void sub_build(int f,int t,int l,int r)
{
    node[f].son[t].lr(l,r); node[f].son[t].val = -inf;
    if( l == r - 1 ) return ;
    int mid = MID(l,r);
    sub_build(f,L(t),l,mid);
    sub_build(f,R(t),mid,r);
}

void Build(int t,int l1,int r1,int l2,int r2)
{
    node[t].lr(l1,r1);
    sub_build(t,1,l2,r2);
    if( l1 == r1 - 1 ) return ;
    int mid = MID(l1,r1);
    Build(L(t),l1,mid,l2,r2);
    Build(R(t),mid,r1,l2,r2);
} 

void sub_updata(int f,int t,int l,int r,int val)
{
	node[f].son[t].val = max(node[f].son[t].val,val);
    if( node[f].son[t].l >= l && node[f].son[t].r <= r ) return ;
    if( node[f].son[t].getlen() == 1 ) return ;
    int mid = node[f].son[t].getmid();
    if( l < mid ) sub_updata(f,L(t),l,r,val);
    if( r > mid ) sub_updata(f,R(t),l,r,val);
}

void Updata(int t,int l1,int r1,int l2,int r2,int val)
{
    sub_updata(t,1,l2,r2,val);
    if( node[t].l >= l1 && node[t].r <= r1 ) return ;
    if( node[t].getlen() == 1 ) return ;
    int mid = node[t].getmid();
    if( l1 < mid ) Updata(L(t),l1,r1,l2,r2,val);
    if( r1 > mid ) Updata(R(t),l1,r1,l2,r2,val);
} 
        
int sub_query(Tnode *node,int t,int l,int r)
{
    if( node[t].l >= l && node[t].r <= r )
        return node[t].val;
    if( node[t].l == node[t].r - 1 ) return -inf;
    int mid = node[t].getmid();
    int ans = -inf;
    if( l < mid )
    	ans = max(ans,sub_query(node,L(t),l,r));
    if( r >= mid )
    	ans = max(ans,sub_query(node,R(t),l,r));
    return ans;
}
 
int Query(int t,int l1,int r1,int l2,int r2)
{
    if( node[t].l >= l1 && node[t].r <= r1 )
        return sub_query(node[t].son,1,l2,r2);
    if( node[t].getlen() == 1 ) return -inf;
    int mid = node[t].getmid();
    int ans = -inf;
    if( l1 < mid )
    	ans = max(ans,Query(L(t),l1,r1,l2,r2));
    if( r1 >= mid )
    	ans = max(ans,Query(R(t),l1,r1,l2,r2));
    return ans;
}
int main()
{
    int k,h,h1,h2;
    int n = 201,m = 1001;
    char ch[5];
    double a,l,a1,a2;
    while( ~scanf("%d",&k) && k )
    {
        init();
        Build(1,100,n,0,m);
        while( k-- )
        {
            scanf("%s",ch);
            if( ch[0] == 'I' )
            {
                scanf("%d%lf%lf",&h,&a,&l);
                int aa = (int)(a*10);
                int ll = (int)(l*10);
                Updata(1,h,h+1,aa,aa+1,ll);
            }
            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(1,h1,h2+1,(int)(a1*10),(int)(a2*10)+1);
                if( ans < -1 )
                    printf("-1\n");
                else
                    printf("%.1lf\n",ans/10.0);
            }
        }
    }
return 0;
}

解题报告转自:http://blog.csdn.net/zxy_snow/article/details/6671188