P2894 [USACO08FEB]Hotel G

\(P2894\) [\(USACO08FEB\)]\(Hotel\) \(G\)

一、题目描述

参考样例，第一行输入\(n，m\) ，\(n\)代表有\(n\)个房间，编号为\(1-\sim n\)，开始都为 空房，\(m\)表示以下有\(m\)行操作，以下 每行先输入一个数 \(op\) ，表示一种操作：

若\(op=1\)，表示查询房间\(query\)，再输入一个数\(x\)，表示在\(1 \sim n\) 房间中找到 长度为\(x\)的连续空房，输出连续\(x\)个房间中左端的房间号，尽量让这个房间号最小:

• 若找不到长度为\(x\)的连续空房，输出\(0\)
• 若找得到，在这\(x\)个空房间中住上人

若\(op=2\)，表示退房，再输入两个数 \(x，y\) 代表 房间号 \(x \sim x+y-1\) 退房，即让房间为空。

二、解题思路

网上的\(build\)代码有两种实现方式:

• 在创建结点时，直接给它的统计属性赋值，因为可以直接获知到它有多少个空白点

//写法1：对叶子进行统计信息设定，其它的父节点统计信息，通过pushup进行递归更新
void build(int u, int l, int r) {
    if (l == r) {
        //初始时都是空房间，连续空房长度就是区间长度:1,
        //从本区间内，左边向右数有1个空白房间，
        //从右边向左数，也有1个空白房间
        tr[u].mx = tr[u].lx = tr[u].rx = 1;
        return;
    }
    int mid = l + r >> 1;
    build(ls, l, mid), build(rs, mid + 1, r);
    //由于只对叶子进行了统计信息设定，而它的上层所有节点的统计信息并没有更新，需要调用一次pushup进行更新统计信息
    pushup(u, l, r);
}

• 创建结点时，不直接给它的统计属性赋值，而是在完成创建后，通过\(pushup\)向上进行统计信息的更新。

//写法2：不准备使用pushup方法递归进行统计信息更新，而是在build时直接对父节点的统计信息直接写入
void build(int u, int l, int r) {
    //因为初始化时都是空房间，所以从左边数空白区间长度就是len
    tr[u].mx = tr[u].lx = tr[u].rx = r - l + 1;
    if (l == r) return;
    int mid = l + r >> 1;
    build(ls, l, mid), build(rs, mid + 1, r);
}

考虑到其它题型，直接给定统计值可能不太现实，不如通过\(pushup\)向上更新统计信息思路统一，建议采用\(pushup\)方法。

三、实现代码

#include <cstdio>
#include <algorithm>

using namespace std;
const int N = 200010;

//宏定义左子树，右子树
#define ls u << 1
#define rs u << 1 | 1

//快读
int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

struct Node {
    int mx;          // 区间最大连续空房数
    int lx, rx;      // 从左开始或从右开始的最大连续空房数
    int lazy;        // lazy:1 开房, :2 退房，0: 默认值
} tr[N];

//根据左右儿子的统计信息，更新父亲的统计信息，也就是更新父亲的统计属性
void pushup(int u, int l, int r) {
    //左后+右前，左半边最大长度，右半边最大长度，三者的最大值
    tr[u].mx = max({tr[ls].rx + tr[rs].lx, tr[ls].mx, tr[rs].mx});

    int mid = l + r >> 1;
    //根据左右儿子的不同情况，汇总生成父亲的三个属性
    //①如果左儿子整体区间都是空的，那么 父亲的左半边最大长度=左儿子区间长度+右儿子左半边最大长度
    if (tr[ls].mx == mid - l + 1)
        tr[u].lx = tr[rs].lx + tr[ls].mx;
    else
        //②否则，左儿子的左半边最大长度，就是父亲的左半边最大长度
        tr[u].lx = tr[ls].lx;

    //③ 如果右儿子的整体区间都是空的，那么 父亲的右半边最长度=右儿子区间长度+左儿子右半边最大长度
    if (tr[rs].mx == r - mid)
        tr[u].rx = tr[ls].rx + tr[rs].mx;
    else //④否则，右儿子的右半边最大长度，就是父亲的右半边最大长度
        tr[u].rx = tr[rs].rx;
}

//向下传递更新信息
void pushdown(int u, int l, int r) {
    if (tr[u].lazy == 0) return; //如果没有下传的懒标记，就不用再向下级传递了

    //如果走到这里，说明lazy标记存在，那么需要向左右儿子传递这个懒标记
    tr[ls].lazy = tr[rs].lazy = tr[u].lazy;

    //在向左右儿子传递了懒标记后，本级的其它统计信息也需要向左右儿子进行传递
    if (tr[u].lazy == 1) { //开房,则全部为1，左、右儿子的三个统计信息都需要修改为0
        tr[ls].mx = tr[ls].lx = tr[ls].rx = 0;
        tr[rs].mx = tr[rs].lx = tr[rs].rx = 0;
    } else { //退房
        int mid = l + r >> 1;
        //退房后，整个区间全是0，左半区间中 左最长=右最长=整个区间长=mid-l+1
        //退房后，整个区间全是0，右半区间中 左最长=右最长=整个区间长=r-mid
        tr[ls].mx = tr[ls].lx = tr[ls].rx = mid - l + 1;
        tr[rs].mx = tr[rs].lx = tr[rs].rx = r - mid;
    };
    //将本节点的懒标记修改为0，表示已经完成了懒标记的向下传递
    tr[u].lazy = 0;
}

//构建线段树
// u:结点号 [l,r]:此结点管辖的范围
//写法1：对叶子进行统计信息设定，其它的父节点统计信息，通过pushup进行递归更新
void build(int u, int l, int r) {
    if (l == r) {
        //初始时都是空房间，连续空房长度就是区间长度:1,
        //从本区间内，左边向右数有1个空白房间，
        //从右边向左数，也有1个空白房间
        tr[u].mx = tr[u].lx = tr[u].rx = 1;
        return;
    }
    int mid = l + r >> 1;
    build(ls, l, mid), build(rs, mid + 1, r);
    //由于只对叶子进行了统计信息设定，而它的上层所有节点的统计信息并没有更新，需要调用一次pushup进行更新统计信息
    pushup(u, l, r);
}

void modify(int u, int l, int r, int x, int y, int c) {
    if (x <= l && y >= r) { //修改区间[x,y]完全包含了当前区间[l,r],那么所有内部节点都需要进行修改
        if (c == 1)         // 1:开房
            tr[u].mx = tr[u].lx = tr[u].rx = 0;         //统计信息全面修改为0，因为全住上人了，没有空的了
        else                                            // 2:退房
            tr[u].mx = tr[u].lx = tr[u].rx = r - l + 1; //整个区间都是空白的，左边最长=右边最长=整个区间最长
        //记得同步修改lazy，准备向下级传递lazy标记
        tr[u].lazy = c;
        return;
    }

    //分裂之前需要下传lazy标记
    pushdown(u, l, r);
    //分裂
    int mid = l + r >> 1;
    if (x <= mid) modify(ls, l, mid, x, y, c);
    if (y > mid) modify(rs, mid + 1, r, x, y, c);

    //向上更新统计信息
    pushup(u, l, r);
}
//以u为根节点的树中，控制范围是[l,r],找出连续空白房间个数>=x的区间,返回此区间的左边界
int query(int u, int l, int r, int x) {
    pushdown(u, l, r); //在查询前，为防止有懒标记未进行正确传递，需提前调用一次pushdown，完成未传递懒标记的正确下传

    int mid = l + r >> 1;
    //因为要获取最小的房间号，所以，必须是左，中，右这个顺序来进行检查，否则可能返回的不是最小房间号
    if (tr[ls].mx >= x) return query(ls, l, mid, x);
    if (tr[ls].rx + tr[rs].lx >= x) return mid - tr[ls].rx + 1; //直接找到开始点
    if (tr[rs].mx >= x) return query(rs, mid + 1, r, x);

    //如果不存在x这么多个连续空白，则返回0
    return 0;
}

int main() {
//文件输入输出
#ifndef ONLINE_JUDGE
    freopen("P2894.in", "r", stdin);
#endif
    // n个房间，m个操作
    int n = read(), m = read();

    //构建线段树，因为有统计信息需要进行初始化，所以需要build
    build(1, 1, n);

    for (int i = 1; i <= m; i++) {
        int op = read();
        if (op == 1) {
            int x = read();
            if (tr[1].mx >= x) {
                int l = query(1, 1, n, x);
                printf("%d\n", l);
                // 1:住人
                modify(1, 1, n, l, l + x - 1, 1);
            } else
                puts("0");
        } else {
            int x = read(), y = read();
            // 2:退房
            modify(1, 1, n, x, x + y - 1, 2);
        }
    }
    return 0;
}