题解：旅店房间管理

题目分析

旅店有 N 个房间，房间排成一排，每个房间都有编号 1 到 N。对于这些房间，可以进行三种操作：

1. 入住操作：给定一个区间，表示入住该区间的房间。
2. 离开操作：给定一个区间，表示离开该区间的房间。
3. 查询操作：查询当前最多连续空闲的房间数。

任务是对这些操作进行处理，最终输出最多连续空闲的房间数。

解题思路

本题的关键在于如何有效地处理操作，尤其是区间内的入住与离开。考虑到有多个区间的操作，使用 线段树 是一个合适的选择。具体来说，我们的线段树每个节点记录三个信息：

• max_len：该区间内最大连续空房间的数量。
• l_c：该区间从左侧开始的连续空房间数量。
• r_c：该区间从右侧开始的连续空房间数量。

每次进行区间的操作时，我们需要更新这些信息。操作包括：

• 入住：将某个区间内的房间标记为已入住。
• 离开：将某个区间内的房间标记为空闲。
• 查询：输出当前区间内最多连续的空房间数。

状态转移与合并

在合并两个区间的线段树节点时，考虑到：

• max_len：最大连续空房间数量是三个值中的最大值：
  • 左子树的 max_len，右子树的 max_len，以及左子树的右侧连续空房间数量加上右子树的左侧连续空房间数量。
• l_c：左子树的左侧连续空房间数量与右子树的左侧连续空房间数量合并。
• r_c：右子树的右侧连续空房间数量与左子树的右侧连续空房间数量合并。

线段树的延迟标记（Lazy Propagation）

为了优化区间操作，避免重复更新整个区间，我们使用了延迟标记（lazy propagation）。每次修改时，只有在需要的时候才将更新应用到子节点。

代码实现

#include <cstdio>
#define mid l + (r - l) / 2
#define lson id << 1, l, mid
#define rson id << 1 | 1, mid + 1, r
using namespace std;

const int MAXN = 16001;

class Node {
public:
    int max_len, l_c, r_c; // max_len: 最大连续空房间, l_c: 左侧连续空房间, r_c: 右侧连续空房间
    Node() {}
    Node(int max_len, int l_c, int r_c) {
        this->max_len = max_len;
        this->l_c = l_c;
        this->r_c = r_c;
    }
} tree[MAXN * 4];

int laze[MAXN * 4]; // 延迟标记

// 求三个数的最大值
int max(int a, int b, int c) {
    a = a > b ? a : b;
    a = a > c ? a : c;
    return a;
}

// 合并两个节点的区间信息
Node max(int id1, int l1, int r1, int id2, int l2, int r2) {
    Node res;
    res.max_len = max(tree[id1].max_len, tree[id2].max_len, tree[id1].r_c + tree[id2].l_c);
    if (tree[id1].l_c == r1 - l1 + 1) res.l_c = tree[id1].l_c + tree[id2].l_c;
    else res.l_c = tree[id1].l_c;
    if (tree[id2].r_c == r2 - l2 + 1) res.r_c = tree[id2].r_c + tree[id1].r_c;
    else res.r_c = tree[id2].r_c;
    return res;
}

// 建立线段树
void build(int id, int l, int r) {
    laze[id] = -1;
    if (l == r) tree[id] = Node(1, 1, 1); // 每个单独的房间初始为空
    else {
        build(lson);
        build(rson);
        tree[id] = max(lson, rson); // 合并左右子树
    }
}

// 传播延迟标记
void pushdown(int id, int l, int r) {
    if (laze[id] == 1) { // 入住操作
        tree[id << 1] = Node(0, 0, 0);
        laze[id << 1] = 1;
        tree[id << 1 | 1] = Node(0, 0, 0);
        laze[id << 1 | 1] = 1;
    }
    else { // 离开操作
        int t_l = l, t_r = mid;
        int d = t_r - t_l + 1;
        tree[id << 1] = Node(d, d, d);
        laze[id << 1] = 0;
        t_l = mid + 1, t_r = r;
        d = t_r - t_l + 1;
        tree[id << 1 | 1] = Node(d, d, d);
        laze[id << 1 | 1] = 0;
    }
    laze[id] = -1;
}

// 更新区间
void updata(int id, int l, int r, int L, int R, int flag) {
    if (R < l || r < L) return; // 不在区间内
    if (L <= l && r <= R) { // 区间完全在当前节点范围内
        if (flag == 1) {
            tree[id] = Node(0, 0, 0); // 入住，标记为空
            laze[id] = 1;
        }
        else {
            tree[id] = Node(r - l + 1, r - l + 1, r - l + 1); // 离开，标记为连续空房
            laze[id] = 0;
        }
        return;
    }
    if (laze[id] != -1) pushdown(id, l, r); // 传播延迟标记
    updata(lson, L, R, flag);
    updata(rson, L, R, flag);
    tree[id] = max(lson, rson); // 合并更新结果
}

int main() {
    int N, P;
    scanf("%d%d", &N, &P);
    build(1, 1, N); // 初始化线段树

    for (int a = 0; a < P; ++a) {
        int op;
        scanf("%d", &op);
        if (op == 3) { // 查询操作，输出当前最大连续空房间数
            printf("%d\n", tree[1].max_len);
        }
        else {
            int a, b;
            scanf("%d%d", &a, &b);
            if (op == 1) updata(1, 1, N, a, a + b - 1, 1); // 入住操作
            else updata(1, 1, N, a, a + b - 1, 0); // 离开操作
        }
    }

    return 0;
}

代码解析

1. 数据结构：

   • Node 类用于表示每个区间的状态，包括最大连续空房间数、从左边起的连续空房间数和从右边起的连续空房间数。
   • laze 数组用于延迟标记，用来标记某个区间是否已经进行过入住或离开操作。

2. 线段树构建与操作：

   • build 函数用于初始化线段树。
   • pushdown 函数用于处理延迟标记的传播，确保子节点的状态与父节点保持一致。
   • updata 函数用于更新某个区间的状态（入住或离开）。
   • max 函数用于合并两个区间的状态。

3. 主函数：

   • 输入操作后，分别执行入住、离开或查询操作。
   • 查询操作时输出当前最大的连续空房间数。

时间复杂度分析

• 每次操作的时间复杂度是 O(log N)，因为线段树的深度为 O(log N)，每次更新或查询的时间复杂度都与树的深度成正比。
• 对于 P 次操作，总的时间复杂度为 O(P log N)，其中 P 是操作的数量，N 是房间的数量。

总结

这道题通过线

段树解决了对区间的多次更新和查询问题，关键是如何处理和合并区间的最大连续空房间数量。通过延迟标记（lazy propagation）优化了区间更新的效率，避免了重复更新。