首页 > 代码库 > Luck and Love （二维线段树）（树套树）

Luck and Love （二维线段树）（树套树）

2024-07-16 03:43:25   222人阅读

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.0
代码不好打啊！！！有木有。哭。纯粹练手速啊。。
#include <iostream>
# include<cstdio>
# include<cstring>
using namespace std;

#define N 300
#define M 3000

# define lch(x) x<<1
# define rch(x)  x<<1|1

struct sonNode
{
    int l, r, val;
    void getlr ( int tl, int tr )
    {
        l = tl; r = tr;
    }
};

struct parentNode
{
    int l, r;
    sonNode son[M];       //树套树
    void getlr ( int tl, int tr )
    {
        l = tl; r = tr;
    }
}node[N];

void sub_build ( int f, int u, int l, int r )
{
    node[f].son[u].getlr ( l, r );
    node[f].son[u].val = -1;        // 储存缘分值
    if ( l == r ) return;
    int mid = ( l + r )>>1;
    sub_build ( f, lch(u), l, mid );
    sub_build ( f, rch(u), mid+1, r );
}

void build ( int f, int l1, int r1, int l2, int r2 )
{
    node[f].getlr ( l1, r1 );
    sub_build ( f, 1, l2, r2 );           //子树建立（父结点，相应子结点）
    if ( l1 == r1 ) return;
    int mid = ( l1 + r1 )>>1;
    build ( lch(f), l1, mid, l2, r2 );
    build ( rch(f), mid+1, r1, l2, r2 );
}

void sub_update ( int f, int u, int pos2, int val )
{
	if ( u > M ) return;          //结束标志
    node[f].son[u].val = max ( node[f].son[u].val, val );
	if ( node[f].son[u].l == pos2 && node[f].son[u].r == pos2 )
	{
		node[f].son[u].val = max ( node[f].son[u].val, val );
		return;
	}
    int mid = ( node[f].son[u].l + node[f].son[u].r )>>1;
    if ( pos2 <= mid )
        sub_update ( f, lch(u), pos2, val );
    else
        sub_update ( f, rch(u), pos2, val );
}
                      //身高     活泼度      缘分值
void update ( int f, int pos1, int pos2, int val )
{
	if ( f > N ) return;    //容易忘记,千万记住
    sub_update ( f, 1, pos2, val );     //子结点更新
	if ( node[f].l == node[f].r ) return;
    int mid = ( node[f].l + node[f].r )>>1;
    if ( pos1 <= mid )
        update ( lch(f), pos1, pos2, val );
    else
        update ( rch(f), pos1, pos2, val );
}

int sub_query ( int f, int u, int l2, int r2 )
{
	if ( u > M ) return -1;
    if ( node[f].son[u].l == l2 && node[f].son[u].r == r2 )
        return node[f].son[u].val;
    int mid = ( node[f].son[u].l + node[f].son[u].r )>>1;
    if ( r2 <= mid )
        return sub_query ( f, lch(u), l2, r2 );
    else if ( l2 > mid )
        return sub_query ( f, rch(u), l2, r2 );
    else
        return max( sub_query(f,lch(u),l2,mid), sub_query(f,rch(u),mid+1,r2) );
}

int query ( int f, int l1, int r1, int l2, int r2 )
{
	if ( f > N ) return -1;    //找不到,返回-1；
    if ( node[f].l == l1 && node[f].r == r1 )
        return sub_query ( f, 1, l2, r2 );
    int mid = ( node[f].l + node[f].r )>>1;
    if ( r1 <= mid )
        return query ( lch(f), l1, r1, l2, r2 );
    else if ( l1 > mid )
        return query ( rch(f), l1, r1, l2, r2 );
    else
        return max ( query(lch(f),l1,mid,l2,r2), query(rch(f),mid+1,r1,l2,r2) );
}
          //   总的来说   主线段树表示身高区间    副线段树表示活泼度区间
           //   然后分别建树，更新，询问  ,只是注意好之间的联系就好
int main ()
{
    char ch[3];
    int m, h, hl, hr, ans;
    double a, l, al, ar;

    while ( scanf("%d",&m) != EOF && m )
    {
        memset(node,0,sizeof(node));
        build ( 1, 100, 200, 0, 1000 );      //根节点，身高区间，活泼度区间
        while ( m-- )
        {
            scanf("%s",ch);
            if ( ch[0] == 'I' )
            {
                scanf("%d%lf%lf", &h, &a, &l );
                update ( 1, h, (int)(a*10), (int)(l*10) );
            }                         //根节点，身高，活泼度，缘分值
            else
            {
                scanf("%d%d%lf%lf", &hl, &hr, &al, &ar);
                if ( hl > hr ) swap ( hl, hr );
                if ( al > ar ) swap ( al, ar );
                ans = query ( 1, hl, hr, (int)(al*10), (int)(ar*10) );
                if ( ans < 0 ) printf("-1\n");    //根节点，身高区间，活泼度区间
                else printf("%.1lf\n", ans/10.0 );
            }
        }
    }
    return 0;
}



联系
我们