C小加

厚德 博学 求真 至善 The bright moon and breeze
posts - 145, comments - 195, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

poj 3667 NYOJ 534 hotel (区间合并线段树)

Posted on 2012-05-04 20:05 C小加 阅读(1841) 评论(0)  编辑 收藏 引用 所属分类: 解题报告

区间合并的线段树题,也是我的第一个区间合并。

题意(转):Bessie等牛到加拿大的桑德贝去增长文化修养外带观赏苏必利尔湖的阳光。按照导游的介绍,Bessie选择了著名的Cumberland大街上的Bullmoose宾馆作为居住的地点。

这座巨型宾馆在一条超长走廊上有N1 ≤ N ≤ 50000)个排成一排的房间,每个房间都能欣赏到苏必利尔湖的好景色。现在所有的房间都是空的。

现在Bessie等旅客们正在不断地发出订房和退房要求。你需要接受M1 ≤ M < 50000)条指令:

每条指令的第一个数字为12。如果是1,后面将有一个整数D表示顾客要预定的房间数。注意,这些房间必须是连续的。如果能够满足旅客的订房要求,输出满足要求的第一个房间的编号(例如,要订房6间,输出3表示3, 4, 5, 6, 7, 8是满足要求的),这样的编号必须是可能的编号里面最靠前的。如果不能满足要求,输出0

如果是2,后面将有两个整数XD表示顾客要退掉X, X + 1, X + 2, ... , X + D - 1D间房。对于这样的指令什么都不输出。

分析:

分别用lsumrsummsum表示区间左边最大连续房间数,区间右边最大连续房间数和区间最大连续房间数。

查询的时候,先找左儿子是否足够,然后如果不够就找左儿子的右区间和右儿子的左区间的和是否足够,如果两个都不够的话就找右儿子(这个时候右儿子就肯定满足了)。

查询结束时要把这个区间的房子更新成已住。

更新的时候和普通的线段树节点更新是一样的,不同的是在更新完子节点后,要把子节点的信息反馈到父节点中。

 

NYOJ中提交TLE,原因居然是宏定义比inline快。

#include<iostream>
#include<cstring>
#include<cctype>
#include<cstdio>
#include<algorithm>
using namespace std;
//没想到我把inline换成宏定义后就AC了,理论上这两个一样的,但是inline的结果却是TLE
#define L(r) r<<1
#define R(r) r<<1|1
//inline int MID(int l,int r){return (l+r)>>1;}
//inline int L(int r){return r<<1;}
//inline int R(int r){return r<<1|1;}
const int MAXM=50005;
typedef struct
{
    int lsum,rsum,msum;//分别表示左边最大房间数,右边最大房间数,整体最大房间数
    int cover;//是否住下
}node;
node tree[MAXM<<2];
void pushDown(int root,int m)//向下更新
{
    if(tree[root].cover==-1) return;//是否已经更新
    tree[L(root)].cover=tree[R(root)].cover=tree[root].cover;
    tree[L(root)].msum=tree[L(root)].lsum=tree[L(root)].rsum=tree[root].cover?0:m-(m>>1);
    tree[R(root)].msum=tree[R(root)].lsum=tree[R(root)].rsum=tree[root].cover?0:(m>>1);
    tree[root].cover=-1;
}
void pushUp(int root,int m)//向上更新
{
    tree[root].lsum=tree[L(root)].lsum;
    tree[root].rsum=tree[R(root)].rsum;
    if(tree[root].lsum==m-(m>>1) ) tree[root].lsum+=tree[R(root)].lsum;
    if(tree[root].rsum==(m>>1) ) tree[root].rsum+=tree[L(root)].rsum;
    tree[root].msum=max(tree[R(root)].lsum+tree[L(root)].rsum,max(tree[L(root)].msum,tree[R(root)].msum) );
}
void Create(int l,int r,int root)//建树过程
{
    tree[root].cover=-1;
    tree[root].lsum=tree[root].rsum=tree[root].msum=r-l+1;
    if(l==r){return;}
    int mid=(l+r)>>1;
    Create(l,mid,L(root));
    Create(mid+1,r,R(root));
}
void update(int ll,int rr,int c,int l,int r,int root)//更新
{
    if(ll<=l&&r<=rr)//如果找到这个范围就直接赋值返回,不向下继续更新
    {
        tree[root].msum=tree[root].lsum=tree[root].rsum=c?0:r-l+1;
        tree[root].cover=c;
        return;
    }
    pushDown(root,r-l+1);//用到这个节点的子节点的时候就向下更新
    int m=(l+r)>>1;
    if(ll<=m) update(ll,rr,c,l,m,L(root));
    if(m<rr) update(ll,rr,c,m+1,r,R(root));
    pushUp(root,r-l+1);//向下更新完后需要把节点信息反馈给父节点
}
int query(int w,int l,int r,int root)//查询满足连续房间数量的最左节点
{
    if(l==r) return l;
    pushDown(root,r-l+1 );//用到这个节点的子节点的时候就向下更新
    int m=(l+r)>>1;
    if(tree[L(root)].msum>=w) return query(w,l,m,L(root));//如果左儿子满足就询问左儿子
    else if(tree[L(root)].rsum+tree[R(root)].lsum>=w) return m-tree[L(root)].rsum+1;//如果左儿子和右儿子之间的数量满足,则范围左儿子右边连续房间第一个的编号
    return query(w,m+1,r,R(root));//如果两者都不满足则询问右儿子
}


int main()
{
    //freopen("in.txt","r",stdin);
    
//freopen("out.txt","w",stdout);
    int n,m;
    while(~scanf("%d %d",&n,&m))
    {
        Create(1,n,1);
        int a,num,x,d,p;
        for(int i=0;i<m;++i)
        {
            scanf("%d",&a);
            if(1==a)
            {
                scanf("%d",&num);
                if(tree[1].msum<num) puts("0");//如果整个区间的最大连续房间数量小于预定的数量就输出0
                else
                {
                    p=query(num,1,n,1);//找到最左节点p
                    printf("%d\n",p);
                    update(p,p+num-1,1,1,n,1);//把已经有人的房间标记一下
                }

            }
            else
            {
                scanf("%d %d",&x,&d);
                update(x,x+d-1,0,1,n,1);//把此范围的房间标记成无人

            }
        }
    }
    return 0;
}


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理