Hdu 1823 Luck and Love-CSDN博客

本文链接：https://blog.csdn.net/csdn364988181/article/details/48347829

本文介绍了一种使用二维线段树解决特定问题的方法，通过在一维线段树的每个节点上构建另一棵线段树来处理身高范围内的最大缘分值查询问题。文中详细展示了线段树的构建、更新及查询过程。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1823

题意：找出身高区间内满足和活泼值条件而且缘分值最高的女孩

思路：二维线段树，也就是一维线段树的每一个节点再保存一颗线段树，一维线段树查询身高区间，然后再该保存该区间的节点构造一颗线段树，用活泼值维护保存最大的缘分值……整体建树不难，就是代码显得又长又丑，一维线段树查询区间，二维线段树单点查询，因为只有一位小数，所以可以乘10再插入，不需要离散化，下面是线段树部分的代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define maxn 210
using namespace std;

struct Node
{
    int l,r;
    double date;
};

struct Tree
{
    int l,r,date;
    Node sub[maxn*20];
} tree[maxn*3];

void buildsub(int id,int root,int l,int r)
{
    tree[id].sub[root].l=l;
    tree[id].sub[root].r=r;
    tree[id].sub[root].date=-1.0;
    if (l==r) return;

    int mid=(l+r)>>1;
    buildsub(id,root<<1,l,mid);
    buildsub(id,root<<1|1,mid+1,r);
}

void build(int root,int l,int r,int ll,int rr)
{//cout<<":"<<root;
    tree[root].l=l;
    tree[root].r=r;
    buildsub(root,1,ll,rr);
    if (l==r) return;
    int mid=(l+r)>>1;
    build(root<<1,l,mid,ll,rr);
    build(root<<1|1,mid+1,r,ll,rr);
}

void update_sub(int id,int root,int act,double val)
{
    if (tree[id].sub[root].l==tree[id].sub[root].r)
    {
        tree[id].sub[root].date=max(val,tree[id].sub[root].date);
        return;
    }

    int mid=(tree[id].sub[root].l+tree[id].sub[root].r)>>1;
    if (act<=mid) update_sub(id,root<<1,act,val);
    else update_sub(id,root<<1|1,act,val);
    tree[id].sub[root].date=max(tree[id].sub[root<<1].date,tree[id].sub[root<<1|1].date);
}


void update(int root,int h,int act,double val)
{
    update_sub(root,1,act,val);
    if (tree[root].l==tree[root].r) return;

    int mid=(tree[root].l+tree[root].r)>>1;
    if (h<=mid) update(root<<1,h,act,val);
    else update(root<<1|1,h,act,val);
}

double que_sub(int id,int root,int l,int r)
{
    if (tree[id].sub[root].l==l && tree[id].sub[root].r==r)
    {
        return tree[id].sub[root].date;
    }

    int mid=(tree[id].sub[root].l+tree[id].sub[root].r)>>1;
    if (r<=mid) return que_sub(id,root<<1,l,r);
    else if (l>mid) return que_sub(id,root<<1|1,l,r);
    else return max(que_sub(id,root<<1,l,mid),que_sub(id,root<<1|1,mid+1,r));
}

double que(int root,int l,int r,int ll,int rr)
{
    if (tree[root].l==l && tree[root].r==r)
    {
        return que_sub(root,1,ll,rr);
    }

    int mid=(tree[root].l+tree[root].r)>>1;
    if (r<=mid) return que(root<<1,l,r,ll,rr);
    else if (l>mid) return que(root<<1|1,l,r,ll,rr);
    else return max(que(root<<1,l,mid,ll,rr),que(root<<1|1,mid+1,r,ll,rr));
}