题解 | Hotel-牛客假日团队赛7C题

C-Hotel_牛客假日团队赛7

https://ac.nowcoder.com/acm/contest/997/C

题目描述

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 $D_i (1 ≤ D_i ≤ 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+D_i-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 $X_i$ and $D_i$ which specify the vacating of rooms $X_i ..X_i +D_i-1 (1 ≤ X_i ≤ N-D_i+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.

输入描述:

* 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_i$ (b) Three space-separated integers representing a check-out: 2, $X_i,$ and $D_i$

输出描述:

* 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.

示例1

输入

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

输出

1
4
7
0
5

解答

题目要求十分简单，并且我们可以清楚地知道这是一道数据结构题。
这道题我们可以用线段树来解决。
具体思路如下：
我们的节点存储三个数据：llen表示该区间最左的一段连续区间长度，rlen表示该区间最右的一段连续区间长度，len表示该区间内最长的一段连续区间长度。
举例：0表示未占，1表示占
011111 它的llen就是0，rlen就是5，len就是5。
这样我们就可以快速的查询了。
线段树一个基本的性质就是要满足区间可以合并相加。
我们这样存储那么合并区间可以分为如下几个状态。

void pushup( int lf, int rg ) {
    int mid = (lf + rg) >> 1;
    llen = ls->llen;
    rlen = rs->rlen;
    if ( llen == (mid-lf+1) ) llen += rs->llen;
    if ( rlen == (rg-mid) ) rlen += ls->rlen;
    len = max(ls->rlen+rs->llen, max(ls->len,rs->len) );
}

注意：
根节点的llen如果左儿子全部可以使用那么还要加上右儿子的左部分
根节点的rlen同理可得。
查询时：我们判断左儿子的长度len是不是大于要求如果大于就在左儿子那边找，否则就判断左儿子的rlen加右儿子的llen是不是大于要求，否则就在右儿子找。
具体程序如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 50005;
int n, m, q, x, y;
struct Node{
    int llen, rlen, len, lazy;
    Node *ls, *rs;
    Node() {
        ls = rs = NULL;
    }
    void pushdown( int lf, int rg ) {
        if ( lazy == 1 || lazy == 0 ) {
            int mid = (lf + rg) >> 1;
            ls->llen = ls->rlen = ls->len = lazy*(mid-lf+1);
            rs->rlen = rs->llen = rs->len = lazy*(rg-mid);
            ls->lazy = rs->lazy = lazy;
            lazy = -1;
        }
    }
    void pushup( int lf, int rg ) {
        int mid = (lf + rg) >> 1;
        llen = ls->llen;
        rlen = rs->rlen;
        if ( llen == (mid-lf+1) ) llen += rs->llen;
        if ( rlen == (rg-mid) ) rlen += ls->rlen;
        len = max(ls->rlen+rs->llen, max(ls->len,rs->len) );
    }
};
Node pool[N * 4], *tail = pool, *root;
Node *build(int lf, int rg) {
    Node *nd = ++tail;
    if ( lf == rg) {
        nd->llen = nd->rlen = nd->len = 1;
        nd->lazy = -1;
    }
    else {
        int mid = (lf + rg) >> 1;
        nd->ls = build(lf, mid);
        nd->rs = build(mid+1, rg);
        nd->llen = nd->rlen = nd->len = nd->ls->llen + nd->rs->llen;
        nd->lazy = -1;
    }
    return nd;
}
int query(Node *nd, int lf, int rg, int len) {
    if ( lf == rg ) return lf;
    nd->pushdown(lf, rg);
    int mid = (lf + rg) >> 1;
    if ( nd->ls->len >= len ) return query(nd->ls, lf, mid, len);
    else if ( nd->ls->rlen + nd->rs->llen >= len ) return mid-nd->ls->rlen+1;
    else return query(nd->rs, mid+1, rg, len);
}
void modify( Node *nd, int lf, int rg, int L, int R, int val ) {
    if ( L <= lf && rg <= R ) {
        nd->llen = nd->rlen = nd->len = val*(rg-lf+1);
        nd->lazy = val;
        return;
    }
    nd->pushdown(lf, rg);
    int mid = (lf + rg) >> 1;
    if ( L <= mid ) modify(nd->ls, lf, mid, L, R, val);
    if ( R > mid ) modify(nd->rs, mid+1, rg, L, R, val);
    nd->pushup(lf, rg);
}
int main() {
    scanf( "%d%d", &n, &m );
    root = build(1, n);
    for ( int i = 1; i <= m; i++ ) {
        scanf( "%d", &q );
        if ( q == 1 ) {
            scanf( "%d", &x ); int pos;
            if ( root->len < x ) printf( "0\n" );
            else {
                pos = query( root, 1, n, x );
                printf( "%d\n", pos );
                modify( root , 1, n, pos, pos+x-1, 0 );
            }
        }
        else {
            scanf( "%d%d", &x, &y );
            modify( root, 1, n, x, x+y-1, 1 );
        }
    }
    return 0;
}

来源：kamisamaxmd