USACO 2008 February Gold / 洛谷 P2894 | Hotel

题目链接：

• 洛谷 P2894

线段树好题。

线段树的节点中存储这几个东西：

• $max$，代表区间最大子段和
• $front$，代表区间最大前缀和
• $back$，代表区间最大后缀和
• $sum$，代表区间和
• $lzy$，代表懒标记，只可能有两种状态：退房与开房

初始化时，将所有节点设置为 $1$，代表是空房。

操作 2 很简单，将 $x$ 至 $x+y-1$ 全部标记为 $1$ 即可。

操作 1 稍微有一些难度，直接放上结论。首先在整段区间上查询最大子段和，如果 $x \le max$，代表有超过 $x$ 个连续的空房，则开始寻找目标房间。

在一个段内寻找空房的最左端时，将整个段分成两部分，分类讨论。

• 左段的最大子段和满足 $x \le max$，递归查询左段。
• 左段的最大后缀和与右段的最大前缀和的和满足 $x \le (back+front)$，连续空房刚好横跨左右段，直接返回。
• 右段的最大子段和满足 $x \le max$，递归查询右段。

查询后区间赋值为 $0$，代表有人。

▶

Code

/******************************
  @GavinCQTD / 2024-12-10 15:55:25
  "P2894 [USACO08FEB] Hotel G" From Luogu
  # https://www.luogu.com.cn/problem/P2894
  1000 ms / 128 MB
******************************/
/* We all make choices, but in the end our choices make us. */

// #pragma GCC optimize(1,2,3,"Ofast","inline")

// #define NDEBUG

#include <iostream>
#include <algorithm>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <cstdio>
#include <cmath>
using namespace std;
inline void pass(){return;}
inline void hold(){while(1);}
#define endl "\n"
#define mp(a,b) make_pair(a,b)
#define ct(a) while(!a.empty()) a.pop()
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
#define cdb cerr<<"Debug: "
#define cwn cerr<<"Warn: "
#define debug(x) cerr<<"In Line "<<__LINE__<<": "<<#x<<" = "<<x<<"\n"
#define sp(a) fixed<<setprecision(a)
#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
#define ll long long
#define ull unsigned long long
#define ld long double
// #define int ll
// #define _debug

int _t,n,m;
struct seg{
    int max=-100000,front,back,sum,lzy;
}tree[2000005];

inline void pushup(int u){
    tree[u].front = max(tree[u*2].front, tree[u*2].sum+tree[u*2+1].front);
    tree[u].back = max(tree[u*2+1].back, tree[u*2+1].sum+tree[u*2].back);
    tree[u].sum = tree[u*2].sum+tree[u*2+1].sum;
    tree[u].max = max(tree[u*2].max, max(tree[u*2+1].max, tree[u*2].back+tree[u*2+1].front));
}
inline void init(int u,int val){
    tree[u].max = val;
    tree[u].front = val;
    tree[u].back = val;
    tree[u].sum = val;
}

void build(int u,int l,int r){
    if(l==r){
        init(u, 1);
        return;
    }
    int mid=(l+r)>>1;
    build(u*2,l,mid);
    build(u*2+1,mid+1,r);
    pushup(u);
}

inline bool inrange(int l,int r,int ql,int qr){return (ql<=l)&&(r<=qr);}
inline bool outofrange(int l,int r,int ql,int qr){return (l>qr)||(r<ql);}

inline seg get(seg l,seg r){
    seg res;
    res.front = max(l.front, l.sum+r.front);
    res.back = max(r.back, r.sum+l.back);
    res.sum = l.sum+r.sum;
    res.max = max(l.max, max(r.max, l.back+r.front));
    return res;
}

inline void maketag(int u,int ul,int ur,int uk){
    if(uk==1){
        tree[u].lzy = 1;
        init(u,-50000);
    }
    else if(uk==2){
        tree[u].lzy = 2;
        init(u,ur-ul+1);
    }
}
inline void pushdown(int u,int ul,int ur){
    int mid=(ul+ur)>>1;
    maketag(u*2,ul,mid,tree[u].lzy);
    maketag(u*2+1,mid+1,ur,tree[u].lzy);
    tree[u].lzy = 0;
}

seg query(int u,int l,int r,int ql,int qr){
    if(inrange(l,r,ql,qr)) return tree[u];
    else if(!outofrange(l,r,ql,qr)){
        int mid=(l+r)>>1;
        pushdown(u,l,r);
        return get(query(u*2,l,mid,ql,qr),query(u*2+1,mid+1,r,ql,qr));
    }
    else return (seg){0,0,0,0,0};
}

int queryst(int u,int l,int r,int qur){
    // assert(u<=n);
    pushdown(u,l,r);
    if(l==r) return l;
    int mid=(l+r)>>1;
    // cerr << l << " " << mid << " " << r << "\n";
    if(query(1,1,n,l,mid).max>=qur){
    // if(0){
        // cerr << "1: " << query(u*2,l,mid,l,mid).max << "\n";
        return queryst(u*2,l,mid,qur);
    }
    else if(tree[u*2].back+tree[u*2+1].front>=qur && tree[u*2].back){
        // cerr << "2: " << tree[u*2].back+tree[u*2+1].front << "\n";
        return mid-tree[u*2].back+1;
    }
    else{
        // cerr << "3: " << query(u*2+1,mid+1,r,mid+1,r).max << "\n";
        return queryst(u*2+1,mid+1,r,qur);
    }
}

void update(int u,int l,int r,int ul,int ur,int uk){
    if(inrange(l,r,ul,ur)) maketag(u,l,r,uk);
    else if(!outofrange(l,r,ul,ur)){
        int mid=(l+r)>>1;
        pushdown(u,l,r);
        update(u*2,l,mid,ul,ur,uk);
        update(u*2+1,mid+1,r,ul,ur,uk);
        pushup(u);
    }
}

// #define queryst(x1,x2,x3,x4) 1

void solve(int testID){
    cin >> n >> m;
    build(1,1,n);
    for(int qur=1;qur<=m;qur++){
        // cerr << ">>> ";
        // for(int i=1;i<=n;i++) cerr<<query(1,1,n,i,i).max<<" ";
        // cerr << "\n>>> ";
        // cerr << query(1,1,n,1,n).max << "\n";
        int op;
        cin >> op;
        if(op==1){
            int x;
            cin >> x;
            if(query(1,1,n,1,n).max>=x){
                int ress=queryst(1,1,n,x);
                cout << ress << "\n";
                update(1,1,n,ress,ress+x-1,1);
            }
            else{
                cout << "0\n";
            }
        }
        else{
            int x,y;
            cin >> x >> y;
            update(1,1,n,x,x+y-1,2);
        }
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    // freopen("PublicDebug.debug", "w", stderr);

    // cout << sp();
    // cerr << sp();

    _t = 1;
    // cin >> _t;

    for(int ran=0;ran<_t;ran++) solve(ran);

    fflush(stdout);
    return 0;
}
CPP