首页 > 代码库 > HDU 3367 Hotel

HDU 3367 Hotel

参照这个博客的做法:请戳 ,还有这个的讲解:

询问区间中满足条件的连续最长区间通常属于区间合并问题。

节点增加4个域,lx:从区间左边数连续空房间的数目。rx:从区间右边数连续空房间的数目。ax:该区间中连续空房间的总数目

col:记录该区间住人的状态,1表示全住满,0表示全空,-1表示有可以住的房间。

查询是否有连续空房间数目num的时候,先查询左边,当tree[v].lx >= num的时候递归左区间;再查询中间,当tree[v*2].lx +tree[v*2+1].rx >= num直接返回最左边端点;最后查询右边,当tree[v].rx>=num递归右区间。col记录该区间的状态,利用了Lazy思想,即当tree[v].col == 1或tree[v].col == 0 时(房间全住满或全不住的情况),要先把这个状态传递到左右子树,并把这个区间的col置为-1。

更新区间[st,st+num-1],即将该区间全置为空或置为满的时候,要先把区间的状态(全空或全满)传递给左右子树,然后递归,最后再把左右子树的状态更新上来,因为子树状态改变,父亲状态肯定也会改变。

看了一下午,终于理解了,看着博客敲得,原谅我是手残=。=

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 D(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

Source

USACO 2008 February Gold
哎,一把心酸泪。涉及到lazy思想,和标记=。=,吃饭回来再注释
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1

const int maxn = 50005;
int lsum[maxn<<2] , rsum[maxn<<2] , msum[maxn<<2];
int cover[maxn<<2];

void PushDown(int rt,int m) {
    if (cover[rt] != -1) {
        cover[rt<<1] = cover[rt<<1|1] = cover[rt];
        msum[rt<<1] = lsum[rt<<1] = rsum[rt<<1] = cover[rt] ? 0 : m - (m >> 1);
        msum[rt<<1|1] = lsum[rt<<1|1] = rsum[rt<<1|1] = cover[rt] ? 0 : (m >> 1);
        cover[rt] = -1;
    }
}
void PushUp(int rt,int m) {
    lsum[rt] = lsum[rt<<1];
    rsum[rt] = rsum[rt<<1|1];
    if (lsum[rt] == m - (m >> 1)) lsum[rt] += lsum[rt<<1|1];
    if (rsum[rt] == (m >> 1)) rsum[rt] += rsum[rt<<1];
    msum[rt] = max(lsum[rt<<1|1] + rsum[rt<<1] , max(msum[rt<<1] , msum[rt<<1|1]));
}
void build(int l,int r,int rt) {
    msum[rt] = lsum[rt] = rsum[rt] = r - l + 1;
    cover[rt] = -1;
    if (l == r) return ;
    int m = (l + r) >> 1;
    build(lson);
    build(rson);
}
void update(int L,int R,int c,int l,int r,int rt) {
    if (L <= l && r <= R) {
        msum[rt] = lsum[rt] = rsum[rt] = c ? 0 : r - l + 1;
        cover[rt] = c;
        return ;
    }
    PushDown(rt , r - l + 1);
    int m = (l + r) >> 1;
    if (L <= m) update(L , R , c , lson);
    if (m < R) update(L , R , c , rson);
    PushUp(rt , r - l + 1);
}
int query(int w,int l,int r,int rt) {
    if (l == r) return l;
    PushDown(rt , r - l + 1);
    int m = (l + r) >> 1;
    if (msum[rt<<1] >= w) return query(w , lson);
    else if (rsum[rt<<1] + lsum[rt<<1|1] >= w) return m - rsum[rt<<1] + 1;
    return query(w , rson);
}
int main() {
    int n,m;
    int u,v,w;
    scanf("%d%d",&n,&m);
    build(1 , n , 1);
    while (m --)
    {
        scanf("%d",&u);
        if (u== 1)
        {
            scanf("%d",&w);
            if (msum[1] < w)
                puts("0");
            else
            {
                int pos= query(w, 1 , n , 1);
                printf("%d\n",pos);
                update(pos , pos + w - 1 , 1 , 1 , n , 1);
            }
        } else {
            scanf("%d%d",&v,&w);
            update(v, v + w - 1 , 0 , 1 , n , 1);
        }
    }
    return 0;
}