题意分析

题目描述了一个酒店房间管理系统，需要处理两种操作：

1. 入住请求（1 Di）：寻找连续的Di间空房，分配最小编号的连续房间，返回起始房号r；若无足够连续空房则返回0
2. 退房请求（2 Xi Di）：释放从Xi开始的连续Di间房

酒店有N间房（1≤N≤50,000），最多处理M个请求（1≤M<50,000），初始所有房间为空。

解题思路

该问题需要高效处理动态区间查询和更新，适合使用线段树数据结构。关键点在于：

1. 维护每个区间的三个信息：
   • ls：从左端点开始的最大连续空房数
   • rs：从右端点开始的最大连续空房数
   • sum：区间内最大连续空房数
2. 入住操作：查询是否存在足够大的连续空房区间，优先选择最小编号的
3. 退房操作：将指定区间标记为空房

线段树需要支持：

• 区间更新（设置房间占用/空闲状态）
• 区间查询（查找满足条件的连续空房）

标程解析

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=50000+5;

struct node {
    int l,r;        // 区间左右端点
    int ls,rs,sum;  // 左连续空房、右连续空房、最大连续空房
}t[maxn<<2];

int lazy[maxn<<2];  // 懒惰标记

void PushUp(int o) {
    // 合并左右子树信息
    t[o].ls=t[o<<1].ls;
    t[o].rs=t[o<<1|1].rs;
    int mid=(t[o].l+t[o].r)>>1;
    
    // 如果左子树全空，可以合并右子树的左连续
    if(t[o].ls==mid-t[o].l+1) t[o].ls+=t[o<<1|1].ls;
    // 如果右子树全空，可以合并左子树的右连续
    if(t[o].rs==t[o].r-mid) t[o].rs+=t[o<<1].rs;
    // 最大连续可能是左/右子树的最大，或中间合并区域
    t[o].sum=max(max(t[o<<1].sum,t[o<<1|1].sum),t[o<<1].rs+t[o<<1|1].ls);
}

void PushDown(int o) {
    if(lazy[o]!=-1) {
        lazy[o<<1]=lazy[o<<1|1]=lazy[o];
        if(lazy[o]) { // 标记为占用
            t[o<<1].ls=t[o<<1].rs=t[o<<1].sum=0;
            t[o<<1|1].ls=t[o<<1|1].rs=t[o<<1|1].sum=0;
        } else { // 标记为空闲
            t[o<<1].ls=t[o<<1].rs=t[o<<1].sum=t[o<<1].r-t[o<<1].l+1;
            t[o<<1|1].ls=t[o<<1|1].rs=t[o<<1|1].sum=t[o<<1|1].r-t[o<<1|1].l+1;
        }
        lazy[o]=-1;
    }
}

void build(int l,int r,int o) {
    lazy[o]=-1;
    t[o].l=l; t[o].r=r;
    t[o].ls=t[o].rs=t[o].sum=r-l+1; // 初始全空
    if(l==r) return;
    int mid=(l+r)>>1;
    build(l,mid,o<<1);
    build(mid+1,r,o<<1|1);
}

void update(int ql,int qr,int l,int r,int flag,int o) {
    if(ql<=l && qr>=r) {
        if(flag) t[o].ls=t[o].rs=t[o].sum=0; // 占用
        else t[o].ls=t[o].rs=t[o].sum=r-l+1; // 释放
        lazy[o]=flag;
        return;
    }
    PushDown(o);
    int mid=(l+r)>>1;
    if(ql<=mid) update(ql,qr,l,mid,flag,o<<1);
    if(qr>mid) update(ql,qr,mid+1,r,flag,o<<1|1);
    PushUp(o);
}

int query(int l,int r,int num,int o) {
    if(l==r) return l; // 找到合适位置
    PushDown(o);
    int mid=(l+r)>>1;
    if(t[o<<1].sum>=num) return query(l,mid,num,o<<1); // 左子树足够
    else if(t[o<<1].rs+t[o<<1|1].ls>=num) return mid-t[o<<1].rs+1; // 中间合并区域足够
    else return query(mid+1,r,num,o<<1|1); // 右子树足够
}

int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    build(1,n,1);
    while(m--) {
        int op;
        scanf("%d",&op);
        if(op==1) { // 入住请求
            int x;
            scanf("%d",&x);
            if(t[1].sum<x) puts("0"); // 无足够连续空房
            else {
                int pos=query(1,n,x,1); // 查询起始位置
                printf("%d\n",pos);
                update(pos,pos+x-1,1,n,1,1); // 标记为占用
            }
        } else { // 退房请求
            int s,t;
            scanf("%d%d",&s,&t);
            update(s,s+t-1,1,n,0,1); // 标记为空闲
        }
    }
    return 0;
}

复杂度分析

• 时间复杂度：每个操作O(logN)
• 空间复杂度：O(N)
• 算法优势：利用线段树高效处理区间查询和更新，适合大规模数据