HDU-1823 Luck and Love 2 D線分ツリー

Luck and Love
Time Limit: 10000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2438    Accepted Submission(s): 627
Problem Description
世界で一番遠い距離は天地の果てではない.
君の前にいる
あなたは私があなたを爱することを知らない
                ―― 張小?
先日、枫氷の叶がWiskeyに结婚式のお知らせをしました.招聘礼は500万に达しましたよ.なんてことだ.でも、天文数字ですね.何MMが押し寄せてきたのか、すぐに万人が路地裏にいて、掃除のおばさんまでにぎやかになりました.
人数が多すぎて、Wiskeyが忙しくて手が回らないので、統計のことは全部楓氷葉子に任せて、自分で家に帰って休みました.これはカエデの氷の葉が忙しくて、彼が処理しなければならないのは2種類の事があって、1つはMMの申し込みを受け入れなければならなくて、2つはWiskeyを手伝って要求に合ったMMの中で縁の最高値を探します.
 
Input
本題には複数のテストデータがあり、最初の数字Mは、次に連続するM個の操作があることを示し、M=0の場合、処理は中止される.
次はオペレータCです.
オペレータが“I”の时、1つのMMが申し込むことを表して、后ろに1つの整数が続いて、Hは身长を表して、2つの浮動小数点数、Aは活発度を表して、Lは縁の値を表します.(100<=H<=200, 0.0<=A,L<=100.0)
オペレータが「Q」である場合、後から4つの浮動小数点数、H 1、H 2は身長区間、A 1、A 2は活発度区間、身長と活発度の要求に合致するMMの中の縁最高値を出力する.(100<=H1,H2<=200, 0.0<=A1,A2<=100.0)
すべての入力浮動小数点数は、小数点数が1つしかありません.
 
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
 
判定には2つの制限条件があるため、2次元線分ツリーを用いてこの問題を解析したが、ここでは問題の記述が少し問題で、後のH 1,H 2は整数型であるべきで、さもなくば高さに10を乗じると、毎回1000*1000の2次元線分が作成され、速度が遅くなる.活発さには10を乗じなければならないに違いない.そうすれば、二分を適用して暴力的に解くことができるからだ.前にbuild()関数をwhile(M-)の中に置いて、それは間違っている惨めですね.ここには、リロードをサポートできる入力フックが書かれています.
コードは次のとおりです.

#include <cstdlib>
#include <cstdio>
#include <cstring>
#define LSON p << 1
#define RSON p << 1 | 1 
#define Max(x, y) (x) > (y) ? (x) : (y)
#define H_TO(x) (x) -100
#define A_TO(x) (int)((x) * 10)
#define MID(x, y) (x) + (y) >> 1
#define TWO(x, y) (x) + (y) << 1
using namespace std;

void CinInt( int &t )
{
    char f = 1, c;
    while( c = getchar(), c < '0' || c > '9' || c == '-' )
    {
        if( c == '-' )
            f = -1;
    }
    t = c - '0';
    while( c = getchar(), c >= '0' && c <= '9' )
        t = t * 10 + c -'0';
    t = t * f;
}

void CinStr( char *s )
{
    int p = -1;
    char c;
    while( c = getchar(), c == ' ' || c == '
' ) ;
    s[++p] = c;
    while( c = getchar(), c != ' ' && c != '
' )
        s[++p] = c;
    s[++p] = '\0';
}

void CinDou( double &d )
{
    d = 0;
    long long t = 0;
    int bit = 0;
    char c;
    while( c = getchar(), ( c < '0' || c > '9' ) && c != '.' ) ;
    if( c != '.' )
    {
        t = c - '0';
        while( c = getchar(), c >= '0' && c <= '9' && c != '.' )
            t = t * 10 + c - '0';
    }
    if( c == '.' )
    {
        while( c = getchar(), c >= '0' && c <= '9' )
        {
            d = d * 10 + c - '0';
            bit++;
        }
    }
    while( bit-- )
        d /= 10;
    d += t;
}


struct node
{
    short l, r, max;
};

struct Node
{
    short l, r;
    node y[2600];
}N[260];

void y_build( node *rt, int p, int l, int r )
{
    rt[p].l = l, rt[p].r = r, rt[p].max = -1;
    if( r - l == 1 ) return;
    int m = MID( l, r );
    y_build( rt, LSON, l, m );
    y_build( rt, RSON, m, r );
}

void build( int p, int l, int r )
{
    y_build( N[p].y, 1, 0, 1001 );
    N[p].l = l, N[p].r = r;
    if( r - l == 1 ) return;
    int m = MID( l, r );
    build( LSON, l, m );
    build( RSON, m, r );
}

void y_modify( node *rt, int p, int l, int r, int L )
{  
    rt[p].max = Max( rt[p].max, L );
    if( rt[p].r - rt[p].l == 1 ) return;
    int m = MID( rt[p].l, rt[p].r );
    if( m >= r )
        y_modify( rt, LSON, l, r, L );
    else
        y_modify( rt, RSON, l, r, L );
}

void modify( int p, int l, int r, int l2, int r2, int L )
{
    y_modify( N[p].y, 1, l2, r2, L );
    if( N[p].r - N[p].l == 1 ) return;
    int m = MID( N[p].l, N[p].r );
    if( m >= r )
        modify( LSON, l, r, l2, r2, L );
    else
        modify( RSON, l, r, l2, r2, L );
}

int y_cal( node *rt, int p, int l, int r )
{
    if( rt[p].l == l && rt[p].r == r )
    {
        return rt[p].max;
    }
    int m = MID( rt[p].l, rt[p].r );
    if( m >= r )
        return y_cal( rt, LSON, l, r );
    else if( m <= l )
        return y_cal( rt, RSON, l, r );
    else
    {
        int a = y_cal( rt, LSON, l, m );
        int b = y_cal( rt, RSON, m, r );
        return Max( a, b );
    }
}

int cal( int p, int l, int r, int l2, int r2 )
{
    if( N[p].l == l && N[p].r == r )
    {
        return y_cal( N[p].y, 1, l2, r2 );
    }
    int m = MID( N[p].l, N[p].r );
    if( m >= r )
        return cal( LSON, l, r, l2, r2 );
    else if( m <= l )
        return cal( RSON, l, r, l2, r2 );
    else
    {
        int a = cal( LSON, l, m, l2, r2 );
        int b = cal( RSON, m, r, l2, r2 );
        return Max( a, b );
    }
}

int main()
{
    int M;
    while( scanf( "%d", &M ), M )
    {
        build( 1, 0, 101 );
        while( M-- )
        {
            char op[5];
            scanf( "%s", op );
            switch( op[0] )
            {
                case 'I':
                {
                    int H;
                    double A, L;
                    CinInt( H ), CinDou( A ), CinDou( L ); 
                    modify( 1, H_TO(H), H_TO(H) + 1, A_TO(A), A_TO(A) + 1, A_TO(L) );
                    break;
                }
                case 'Q':
                {
                    int H1, H2;
                    double A1, A2;
                    CinInt( H1 ), CinInt( H2 ), CinDou( A1 ), CinDou( A2 );
                    if( H1 > H2 )
                    {
                        int t = H1;
                        H1 = H2;
                        H2 = t;
                    }
                    if( A1 - A2 > 1e-6 )
                    {
                        double t = A1;
                        A1 = A2;
                        A2 = t;
                    }
                    int ans = cal( 1, H_TO( H1 ), H_TO( H2 ) + 1, A_TO( A1 ), A_TO( A2 ) + 1 ); 
                    printf( ans == -1 ? "-1
" : "%.1lf
", ans / 10.0 );
                }
            }
        }
    }
    return 0;
}