POJ 3667 Hotel（线段树的合并+lazy tag）【很详细！！】

浅浅的花香味﹌ 2022-06-13 09:39 171阅读 0赞

Description

The cows are journeying north to Thunder Bay in Canada to gain cultural enrichment and enjoy a vacation on the sunny shores of Lake Superior. Bessie, ever the competent travel agent, has named the Bullmoose Hotel on famed Cumberland Street as their vacation residence. This immense hotel has *N* (1 ≤ *N* ≤ 50,000) rooms all located on the same side of an extremely long hallway (all the better to see the lake, of course).

The cows and other visitors arrive in groups of size *Di* (1 ≤ *Di* ≤ N) and approach the front desk to check in. Each group *i* requests a set of *Di* contiguous rooms from Canmuu, the moose staffing the counter. He assigns them some set of consecutive room numbers *r*..*r*\+*Di*\-1 if they are available or, if no contiguous set of rooms is available, politely suggests alternate lodging. Canmuu always chooses the value of *r* to be the smallest possible.

Visitors also depart the hotel from groups of contiguous rooms. Checkout *i* has the parameters *Xi* and *Di* which specify the vacating of rooms *Xi* ..*Xi* \+*Di*\-1 (1 ≤ *Xi* ≤ *N*\-*Di*\+1). Some (or all) of those rooms might be empty before the checkout.

Your job is to assist Canmuu by processing *M* (1 ≤ *M* < 50,000) checkin/checkout requests. The hotel is initially unoccupied.

Input

\* Line 1: Two space-separated integers: *N* and *M*  
\* Lines 2..*M*\+1: Line *i*\+1 contains request expressed as one of two possible formats: (a) Two space separated integers representing a check-in request: 1 and *Di* (b) Three space-separated integers representing a check-out: 2, *Xi*, and *Di*

Output

\* Lines 1.....: For each check-in request, output a single line with a single integer *r*, the first room in the contiguous sequence of rooms to be occupied. If the request cannot be satisfied, output 0.

Sample Input

10 6
    1 3
    1 3
    1 3
    1 3
    2 5 5
    1 6

Sample Output

1
    4
    7
    0
    5

题目大意：

有一家旅馆，有N个房间，一开始全空，要入住人，输入1为入住，接下来数字为入住人数，要求要为连续房间号，如果有空的连续的房间，输出最左边的房间号，否则输出0，输入2为清空操作，后面两个数字为起始清空的位置和清空的房间数（没人的也算）

分析：

暑假集训队线段树训练题。。。之前也就写了两个线段树的入门题。。毫无思路，那就百度吧，结果搜出来几乎都没什么解释。。看不懂，快要崩溃了，于是我就静下心来专心看了一个博主的文章。。。。我勒个去看了我一个晚上加一个上午才算是理解了，运用了线段树的区间合并和lazy tag延迟标记的思想，代码里面有详细的解释，代码是照着别人的代码以我的风格写的，注释是我的理解，算是做了一遍程序翻译吧qaq，原博客http://www.cnblogs.com/yewei/archive/2012/05/05/2484471.html

题解：

以下是从博客引用：

思路：利用线段树建立模型，维护最大连续区间长度，其中区间长度就是对应的房间数目，并且对应区间中最左边的断点就是answer，同时因为需要求出连续区间的最大长度，因此每次PushUp时都将左右区间合并，lsum维护左区间的最大长度，rsum维护右区间的最大长度，sum维护区间1…N中的最大连续区间长度，Tag标志对应区间是否为空（没有住客）

具体实现过程：

BuildTree：建立一颗线段树，其中lsum，rsum，sum初始化为对应区间的长度

Query ：询问是否有长度为a的连续区间，如果有，返回对应区间的最左边的断点

UpData ：更新线段树的信息

PushUp ：将左右子区间合并

PushDown ：标志向下传，延迟标志，简单来说就是先标志，然后等到下次询问或者更新时再去更新线段树

代码：

#include<iostream>
    #include<stdio.h>
    #include<cstring>
    #include<string>
    #include<queue>
    #include<map>
    #include<stack>
    #include<math.h>
    #include<algorithm>
    using namespace std;
    const int MAX=1e4*5;
    struct node
    {
        int sum,lsum,rsum,tag;//lsum 和 rsum分别代表从左数和从右数剩余的空间数
    }t[MAX*3];
    void Build(int l,int r,int num)
    {
        t[num].lsum=t[num].rsum=t[num].sum=r-l+1;//递归建树,把所有的tag赋值为-1,把所有空余长度赋值为全区间长度
        t[num].tag=-1;
        if(l==r)
            return;
        int mid=(l+r)/2;
        Build(l,mid,num*2);
        Build(mid+1,r,num*2+1);
    }
    void Pushdown(int num,int len)//lazy tag,把父节点的状态传递下去
    {
        if(t[num].tag!=-1)
        {
            int lson=num*2,rson=num*2+1;//表示左右子节点
            t[lson].tag=t[rson].tag=t[num].tag;
            t[lson].lsum=t[lson].rsum=t[lson].sum=t[num].tag?0:len-(len/2);//父节点为空,把左右区间空余长度赋值为最大
            t[rson].lsum=t[rson].rsum=t[rson].sum=t[num].tag?0:len/2;
            t[num].tag=-1;
        }
    }
    int query(int len,int l,int r,int num)//询问查找满足长度的区间最左端
    {
        if(l==r)
            return 1;
        Pushdown(num,r-l+1);//把上一次询问没有传递的状态传递下去
        int mid=(l+r)/2;
        int lson=num*2,rson=num*2+1;
        if(t[lson].sum>=len)//优先查找左区间是否有空余空间
            return query(len,l,mid,lson);
        else if(t[lson].rsum+t[rson].lsum>=len)//查找左区间的右部分和有区间的左部分是否能形成需要空间
            return mid-t[lson].rsum+1;
        else
            return query(len,mid+1,r,rson);//查找右区间
    }
    void Pushup(int num,int len)//区间合并,更新父节点的空间数
    {
        int lson=num*2,rson=num*2+1;
        t[num].lsum=t[lson].lsum;
        t[num].rsum=t[rson].rsum;
        if(t[num].lsum==len-len/2)//如果左区间全部为空，合并右子树的从左数的区间
            t[num].lsum+=t[rson].lsum;
        if(t[num].rsum==len/2)
            t[num].rsum+=t[lson].rsum;
        t[num].sum=max(t[lson].rsum+t[rson].lsum,max(t[lson].sum,t[rson].sum));//更新父节点空间数
    }
    void Update(int L,int R,int c,int l,int r,int num)//更新节点信息，L,R为更新范围,l,r为num节点对应的左右范围
    {
        if(L<=l&&r<=R)
        {
            t[num].lsum=t[num].rsum=t[num].sum=c?0:r-l+1;//判断c为1为入住操作，0为清空操作
            t[num].tag=c;
            return;
        }
        Pushdown(num,r-l+1);//向下更新子节点
        int mid=(l+r)/2;
        int lson=num*2,rson=num*2+1;
        if(L<=mid)
            Update(L,R,c,l,mid,lson);
        if(R>mid)
            Update(L,R,c,mid+1,r,rson);
        Pushup(num,r-l+1);//合并区间
    }
    int main()
    {
        int n,k,i,x,y;
        scanf("%d%d",&n,&k);
        Build(1,n,1);
        for(i=1;i<=k;i++)
        {
            scanf("%d",&x);
            if(x==1)
            {
                scanf("%d",&y);
                if(y<=t[1].sum)
                {
                    int pos=query(y,1,n,1);
                    printf("%d\n",pos);
                    Update(pos,pos+y-1,1,1,n,1);
                }
                else
                    printf("0\n");
            }
            else
            {
                scanf("%d%d",&x,&y);
                Update(x,x+y-1,0,1,n,1);
            }
        }
        return 0;
    }