poj 3667_Hotel_线段树

发布于 2017-08-16  6 次阅读


题目描述

有一间旅馆,旅馆内有n间排成一排的房间,一开始全为空。现在有m个要求:

1 d表示询问旅馆内是否有连续d间空房间,有的话则输出最小的一个r,满足从r开始连续d间房间均为空,同时会有人入住这d间房。若无法被满足,则输出0.

2 l r表示把[l,l + r]内的房间全部设为空。


 

思路

我们可以用线段树记录下每一个区间的数个值:
1.t.l 记录每一个区间的左区间从左端开始的连续空房间数量

2.t.r 记录每一个区间的右区间从右端开始的连续空房间数量

3.t.tot 记录每一个区间的最大连续空房间的数量

 

 

首先我们来考虑查找:

对于一个询问x,我们要找到最靠左的连续x个空房间

那么根据题意,我们显然要找尽可能靠左的,所以我们可以先判断左区间的tot,如果tot>=x那么我们显然是可以往左区间找的

如果无法往左区间找的话,我们也不可以直接往右区间找,因为一个连续的区间可能在线段树里面被分成了两份

这时我们就要判断一下左区间的r和右区间的l相加>=x 如果满足的话,那么我们要找的最左端就在分开的位置(mid) - 左区间的r + 1;

最后我们再判断是否在右区间中

以上的步骤中,显然如果t[1].tot

 

 

然后我们在来考虑两种更改

一种是将我们上面说的区间的点全部付为有人住

我们可以设我们找到的最左的点为 left, 那么我们其实就是将区间[left, left + x - 1] 改为有人住

我们可以直接将这个区间里的全部状态(l, r, tot)改为0

另外一种是将一段区间全部改为没有人住

对于这一个区间,我们可以将其的全部状态(l, r, tot)改为当前区间的长度 r-l+1,因为我们进行更改的区间显然是全部为空房间的,所以这一个付值很显然是没有问题的

对于下传每个区间的状态我们可用用lazy来完成,对于lazy的方式这里就不讲了,不打lazy的话可能也不会有问题

然后我们在来考虑向上传递状态

显然在一般的情况下,当前区间的l == 左区间的l 右区间类似

然后我们考虑如果左右区间中有整个区间都为空房间的情况,这时我们当前的区间(设为t[p])就可以有

1.当左区间全为空房间t[p].l+=t[p<<1|1].l

对于有区间类似

最后我们考虑每一个区间(设为t[p])的tot,t[p].tot=max(max(t[p<<1].tot, t[p<<1|1].tot), t[p<<1].r+t[p<<1|1].l)

简单来说就是左右区间的tot和两个区间合并后中间的部分所构成的连续空房间进行比较,取最大值即可


 

#include 
#define maxn 1500001
#define max(x, y) (x) > (y) ? (x) : (y)
#define min(x, y) (x) < (y) ? (x) : (y)
struct tree
{
    int tot, l, r, cover;
}t[maxn];
int ll = 0;
int make(int p, int l, int r)
{
    t[p].cover = -1;
    t[p].tot = t[p].l = t[p].r = r - l + 1;
    if (l == r)
    {
        return 0;
    }
    int m = (l + r) >> 1;
    make(p << 1, l, m);
    make(p << 1 | 1, m + 1, r);
}
int pushdown(int p, int k)
{
    if (t[p].cover != -1)
    {
        t[p << 1].cover = t[p << 1 | 1].cover = t[p].cover;
        if (t[p].cover == 0)
        {
            t[p << 1].l = t[p << 1].r = t[p << 1].tot = k - (k >> 1);
            t[p << 1 | 1].l = t[p << 1 | 1].r = t[p << 1 | 1].tot = (k >> 1);
        }
        else
        {
            t[p << 1].l = t[p << 1].r = t[p << 1].tot = t[p << 1 | 1].l = t[p << 1 | 1].r = t[p << 1 | 1].tot = 0;
        }
        t[p].cover = -1;
    }
    return 0;
}
int find(int p, int l, int r, int x)
{
    if (l == r)
        return 1;
    pushdown(p, r - l + 1);
    int m = (l + r) >> 1;
    if (t[p << 1].tot >= x) return find(p << 1, l, m, x);
    else if(t[p << 1].r + t[p << 1 | 1].l >= x) return m - t[p << 1].r + 1;
    else return find(p << 1 | 1, m + 1, r, x);
}
int pushup(int p, int k)
{
    t[p].l = t[p << 1].l;
    t[p].r = t[p << 1 | 1].r;
    if (t[p].l == k - (k >> 1))
        t[p].l += t[p << 1 | 1].l;
    if (t[p].r == (k >> 1))
        t[p].r += t[p << 1].r;
    t[p].tot = max(t[p << 1].r + t[p << 1 | 1].l, max(t[p << 1].tot, t[p << 1 | 1].tot));
    return 0;
}
int change(int p, int l, int r, int x, int y, int c)
{
    if (x == l && r == y)
    {
        if (c == 1)
            t[p].tot = t[p].l = t[p].r = 0;
        else t[p].tot = t[p].l = t[p].r = r - l + 1;
        t[p].cover = c;
        return 0;
    }    
    pushdown(p, r - l + 1);
    int m = (l + r) >> 1;
    if (y <= m) change(p << 1, l, m, x, y, c);
    else if (x > m) change(p << 1 | 1, m + 1, r, x, y, c);
    else 
    {
        change(p << 1, l, m, x, m, c);
        change(p << 1 | 1, m + 1, r, m + 1, y, c);
    }
    pushup(p, r - l + 1);
}
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    make(1, 1, n);
    for (int i = 1; i <= m; i++)
    {
        int x;
        scanf("%d", &x);
        if (x == 1)
        {
            int y;
            scanf("%d", &y);
            if (t[1].tot < y) printf("0\n");
            else
            {
                int l = find(1, 1, n, y);
                printf("%d\n", l);
                change(1, 1, n, l, y + l - 1, 1);
            }
        }
        else 
        {
            int y, z;
            scanf("%d%d", &y, &z);
            change(1, 1, n, y, y + z - 1, 0);
        }
    }
    return 0;
}

 


 

]]>


「墨泼三千烟火,许你一世迷离」