【题解】P2894 [USACO08FEB]Hotel G

引入

这是一道让我记忆深刻的题目。

是上海市某知名信息学教练虐待刚学OI半年的萌新的题目。(强烈谴责此类行为!)

传送门

解题思路

既然是区间问题,很容易想到线段树。但是该如何维护线段树呢?

我们令每一个结构体tree的数组记录区间最长空房sum,从左端点为最左端点的最长空房ls,以右端点为最右端点的最长空房rs。(最好记录下当前区间长度,否则计算时很容易写错)

这里线段树的更新就不说了,先说查询。

查询

对于每个节点的两个儿子节点,其最大值必定在其 左儿子的sum,右儿子的sum,左儿子的rs+右儿子的ls 中。于是一层层查询下去即可。

lazy标记下传

lazy标记就标记这一个区间应该变成什么,然后分情况讨论。这个很简单,无需多讲。

子节点更新父节点

父节点的sum:父节点的sum必定在 左儿子的sum,右儿子的su,左儿子的rs+右儿子的ls中。

父节点的ls:如果左儿子的房间中全有人,则 父节点的ls=左儿子的sum+右儿子的ls;否则 父节点的ls=左儿子的ls

父节点的rs:类似父节点的ls

代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct tree{
    int ls,rs,sum;
    int len;
}tr[400005];
int lazy[400005];
void build(int l,int r,int now){
    tr[now].len=r-l+1;
    tr[now].sum=(r-l+1),tr[now].ls=(r-l+1),tr[now].rs=(r-l+1);
    if(l==r)return ;
    int mid=(l+r)/2;
    build(l,mid,now*2);
    build(mid+1,r,now*2+1);
}
void update(int l,int r,int now){
    if(tr[now*2].sum==tr[now*2].len)tr[now].ls=tr[now*2].sum+tr[now*2+1].ls;
    else tr[now].ls=tr[now*2].ls;
    if(tr[now*2+1].sum==tr[now*2+1].len)tr[now].rs=tr[now*2+1].sum+tr[now*2].rs;
    else tr[now].rs=tr[now*2+1].rs;
    tr[now].sum=max(max(tr[now*2].sum,tr[now*2+1].sum),tr[now*2].rs+tr[now*2+1].ls);
}
void down(int l,int r,int now){
    int mid=(r-l+1)/2;
    if(lazy[now]==2){
        tr[now*2].sum=tr[now*2].ls=tr[now*2].rs=tr[now*2+1].sum=tr[now*2+1].ls=tr[now*2+1].rs=0;
        lazy[now*2]=lazy[now*2+1]=2;
    }else if(lazy[now]==1){
        tr[now*2].sum=tr[now*2].ls=tr[now*2].rs=tr[now*2].len;
        tr[now*2+1].sum=tr[now*2+1].ls=tr[now*2+1].rs=tr[now*2+1].len;
        lazy[now*2]=lazy[now*2+1]=1;
    }
    lazy[now]=0;
}
void add(int l,int r,int gl,int gr,int now,int sum){
    if(gl<=l&&r<=gr){
        if(sum==2)tr[now].sum=0,tr[now].ls=0,tr[now].rs=0;
        else if(sum==1) tr[now].sum=r-l+1,tr[now].ls=r-l+1,tr[now].rs=r-l+1;
        lazy[now]=sum;
        return ;
    }
    down(l,r,now);
    int mid=(l+r)/2;
    if(gl<=mid)add(l,mid,gl,gr,now*2,sum);
    if(gr>mid) add(mid+1,r,gl,gr,now*2+1,sum);
    update(l,r,now);
}
int query(int l,int r,int now,int sum){
    if(l==r)return l;
    down(l,r,now);
    int mid=(l+r)/2;
    if(tr[now*2].sum>=sum)return query(l,mid,now*2,sum);
    else if(tr[now*2].rs+tr[now*2+1].ls>=sum)return mid-tr[now*2].rs+1;
    else return query(mid+1,r,now*2+1,sum);
}
int main(){
    cin>>n>>m;
    int op,x,y;
    int tmp;
    build(1,n,1);
    for(int i=1;i<=m;i++){
        cin>>op;
        if(op==1){
            cin>>x;
            tmp=query(1,n,1,x);
            if(tmp+x-1>n){
                cout<<0<<endl;
            }else{
                cout<<tmp<<endl;
                add(1,n,tmp,tmp+x-1,1,2);
            }
        }else if(op==2){
            cin>>x>>y;
            add(1,n,x,x+y-1,1,1);
        }
    }
    return 0;
}

本文链接:http://kaispace.com.cn/index.php/archives/664/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者