题解：P2894 [USACO08FEB] Hotel G

FTAC · 2026-10-24 17:12:01 · 题解

给一个分块做法。

对于每个块，分别维护这个块前缀 / 后缀连续空房的个数和块内最大的连续空房长度。

对于修改操作，散块直接暴力重构，整块则打上标记，顺便更新一下这个块维护的值。

对于查询操作，直接遍历每个块求出答案，如果答案在一个块里面就遍历这个块找到答案，否则，答案一定是由一段后缀 + 若干个整块 + 一段前缀组成，在遍历时顺便求出即可。

时间复杂度 O(q\sqrt n)。

代码：

#include<bits/stdc++.h>
using namespace std;
const int len=223;
int a[50010],bel[50010],L[310],R[310],lmx[310],rmx[310],mx[310],tag[310],n,q;
void pushtag(int x){
    if(tag[x]==-1)return;
    if(tag[x]==1){
        for(int i=L[x];i<=R[x];i++)a[i]=1;
        lmx[x]=rmx[x]=mx[x]=0,tag[x]=-1;
        return;
    }
    for(int i=L[x];i<=R[x];i++)a[i]=0;
    lmx[x]=rmx[x]=mx[x]=R[x]-L[x]+1,tag[x]=-1;
    return;
}
void pushup(int x){
    lmx[x]=rmx[x]=0;
    for(int i=L[x];i<=R[x];i++){
        if(a[i])break;
        lmx[x]++;
    }
    for(int i=R[x];i>=L[x];i--){
        if(a[i])break;
        rmx[x]++;
    }
    mx[x]=max(lmx[x],rmx[x]);
    int cnt=0;
    for(int i=L[x]+lmx[x]+1;i<=R[x]-rmx[x];i++)cnt=(a[i]?0:cnt+1),mx[x]=max(mx[x],cnt);
    return;
}
void update(int x,int y){
    pushtag(bel[x]),pushtag(bel[y]);
    if(bel[x]==bel[y]){
        for(int i=x;i<=y;i++)a[i]=1;
        pushup(bel[x]);
        return;
    }
    for(int i=x;i<=R[bel[x]];i++)a[i]=1;
    for(int i=L[bel[y]];i<=y;i++)a[i]=1;
    pushup(bel[x]),pushup(bel[y]);
    for(int i=bel[x]+1;i<bel[y];i++){
        lmx[i]=rmx[i]=mx[i]=0,tag[i]=1;
    }
    return;
}
void update2(int x,int y){
    pushtag(bel[x]),pushtag(bel[y]);
    if(bel[x]==bel[y]){
        for(int i=x;i<=y;i++)a[i]=0;
        pushup(bel[x]);
        return;
    }
    for(int i=x;i<=R[bel[x]];i++)a[i]=0;
    for(int i=L[bel[y]];i<=y;i++)a[i]=0;
    pushup(bel[x]),pushup(bel[y]);
    for(int i=bel[x]+1;i<bel[y];i++){
        lmx[i]=rmx[i]=mx[i]=R[i]-L[i]+1,tag[i]=0;
    }
    return;
}
int qry(int x,int y){
    int cnt=0,pos=L[x];
    for(int i=L[x];i<=R[x];i++){
        if(a[i])cnt=0,pos=i;
        else cnt++;
        if(cnt>=y)return pos+1;
    }
    return 0;
}
int query(int x){
    int ans=0,p=1;
    for(int i=1;i<=bel[n];i++){
        if(mx[i]==R[i]-L[i]+1){
            ans+=mx[i];
            if(ans>=x)return p;
        }else{
            ans+=lmx[i];
            if(ans>=x)return p;
            if(mx[i]>=x)return qry(i,x);
            p=R[i]-rmx[i]+1,ans=rmx[i];
            if(ans>=x)return p;
        }
    }
    return 0;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++)bel[i]=(i-1)/len+1;
    for(int i=1;i<=bel[n];i++){
        L[i]=(i-1)*len+1,R[i]=min(i*len,n);
        lmx[i]=rmx[i]=mx[i]=R[i]-L[i]+1,tag[i]=-1;
    }
    for(int i=1;i<=q;i++){
        int op,x,y;
        cin>>op>>x;
        if(op==1){
            int tmp=query(x);
            cout<<tmp<<'\n';
            if(tmp)update(tmp,tmp+x-1);
        }else cin>>y,update2(x,x+y-1);
    }
    return 0;
}