P2894 [USACO08FEB] Hotel G

P3071 [USACO13JAN] Seating G

题目描述

第一行输入 \(n,m\)，\(n\) 代表有 \(n\) 个房间 \((1\leq n \leq 50,000)\)，编号为 \(1 \sim n\)，开始都为空房，\(m\) 表示以下有 \(m\) 行操作 \((1\leq m < 50,000)\)，以下每行先输入一个数 \(i\) ，表示一种操作：

若 \(i\) 为 \(1\)，表示查询房间，再输入一个数 \(x\)，表示在 \(1,2,...,n\) 房间中找到长度为 \(x\) 的连续空房，输出连续 \(x\) 个房间中左端的房间号，尽量让这个房间号最小，若找不到长度为 \(x\) 的连续空房，输出 \(0\)。若找得到，在这 \(x\) 个空房间中住上人。

若 \(i\) 为 \(2\)，表示退房，再输入两个数 \(x,y\) 代表房间号 \(x \sim x+y-1\) 退房，即让房间为空。

你需要对每个输入 \(1\) 输出对应的答案。

Solution:

细节有点多的线段树题。维护一下区间子段和，然后查询的时候由于它寻问的是所有满足条件的区间中左端点的最小值，所以我们在查询时应该取区间的最大子段和的起点 \(t[x].pos\) ,中间两端合并的起点 \(mid-t[ls].rmx+1\) 来更新答案，然后如果左子树满足条件的话就查询左子树，反之查询右子树。如果区间的最大子段和 \(t[x].mx<k\) 的话就直接返回。

然后注意一下pushdownd的细节就可以 AC 本题

Code:

#include<bits/stdc++.h>
const int N=4e5+5;
const int inf=1e9;
using namespace std;
int n,m,cnt,rt;
int a[N];
map<int,int> Map;
//Segment_Tree
struct Tree{
    int lmx,rmx,mx,pos,tag;
    int ls,rs;
}t[N<<4];
#define ls t[x].ls
#define rs t[x].rs
void add(int &x,int l,int r)
{
    if(x)return ;
    x=++cnt;
    t[x].lmx=t[x].rmx=t[x].mx=r-l+1;
    t[x].pos=l;
}
void pushdown(int x,int l,int r)
{
    if(!t[x].tag||l==r)return ;
    int mid=l+r>>1;
    if(!ls)add(ls,l,mid);
    if(!rs)add(rs,mid+1,r);
    if(t[x].tag==1)
    {
        t[x].tag=0;
        t[ls].tag=t[rs].tag=1;
        t[ls].lmx=t[ls].rmx=t[ls].mx=0;
        t[rs].lmx=t[rs].rmx=t[rs].mx=0;
        t[ls].pos=t[rs].pos=inf;
    }
    if(t[x].tag==-1)
    {
        t[x].tag=0;
        t[ls].tag=t[rs].tag=-1;
        t[ls].lmx=t[ls].rmx=t[ls].mx=mid-l+1;
        t[rs].lmx=t[rs].rmx=t[rs].mx=r-mid;
        t[ls].pos=l;
        t[rs].pos=mid+1;
    }

}
void push_up(int x,int l,int r)
{
    int mid=l+r>>1;
    t[x].lmx=t[ls].lmx+ (t[ls].mx==(mid-l+1) ? t[rs].lmx : 0);
    t[x].rmx=t[rs].rmx+ (t[rs].mx==(r-mid)   ? t[ls].rmx : 0);
    t[x].mx=0;t[x].pos=inf;
    if(t[ls].mx>t[x].mx)
    {
        t[x].mx=t[ls].mx;
        t[x].pos=t[ls].pos;
    }
    if(t[ls].rmx+t[rs].lmx==t[x].mx){t[x].pos=min(t[x].pos,mid-t[ls].rmx+1);}
    if(t[ls].rmx+t[rs].lmx>t[x].mx)
    {
        t[x].mx=t[ls].rmx+t[rs].lmx;
        t[x].pos=mid-t[ls].rmx+1;
    }
    if(t[rs].mx>t[x].mx)
    {
        t[x].mx=t[rs].mx;
        t[x].pos=t[rs].pos;
    }
}
void upd(int &x,int l,int r,int L,int R,int k)
{
    if(!x)add(x,l,r);
    if(L<=l&&r<=R)
    {
        if(k)
        {
            t[x].lmx=t[x].rmx=t[x].mx=r-l+1;
            t[x].pos=l;t[x].tag=-1;
        }
        else
        {
            t[x].lmx=t[x].rmx=t[x].mx=0;
            t[x].tag=1;t[x].pos=inf;
        }
        return ;
    }
    int mid=l+r>>1;
    add(ls,l,mid);add(rs,mid+1,r);
    pushdown(x,l,r);
    if(L<=mid)upd(ls,l,mid,L,R,k);
    if(mid<R) upd(rs,mid+1,r,L,R,k);
    push_up(x,l,r);
}
int tag=0;
void query(int x,int l,int r,int k,int &res)
{
    if(t[x].mx<k)return ;
    int mid=l+r>>1;
    res=min(res,t[x].pos);
    //if(t[x].pos==178)cout<<"query:"<<x<<":"<<t[x].pos<<" "<<l<<" "<<r<<" "<<t[ls].lmx<<" "<<t[ls].mx<<" : "<<t[rs].rmx<<" "<<t[rs].mx<<"\n";
    pushdown(x,l,r);
    //if(mid-t[ls].rmx+1==178)cout<<"query:"<<t[x].pos<<" "<<l<<" "<<r<<" "<<t[ls].lmx<<" "<<t[ls].mx<<" : "<<t[rs].rmx<<" "<<t[rs].mx<<"\n";
    if(t[ls].rmx+t[rs].lmx>=k){res=min(res,mid-t[ls].rmx+1);}
    if(t[ls].mx>=k){query(ls,l,mid,k,res);}
    if(t[ls].mx<k&&t[rs].mx>=k){query(rs,mid+1,r,k,res);}
}
void work()
{
    cin>>n>>m;
    add(rt,1,n);
    for(int i=1,k,l,r;i<=m;i++)
    {
        scanf("%d",&k);
        if(k==1)
        {
            tag++;
            scanf("%d",&r);
            //cout<<"k="<<r<<"\n";
            if(t[rt].mx<r){printf("%d\n",0);continue;}
            l=inf;
            query(rt,1,n,r,l);
            r+=l-1;
            upd(rt,1,n,l,r,0);
            //cout<<"book:"<<l<<" "<<r<<"\n";
            printf("%d\n",l);
        }
        else
        {
            scanf("%d%d",&l,&r);
            r+=l-1;
            upd(rt,1,n,l,r,1);
            //cout<<"exit:"<<l<<" "<<r<<"\n";
        }
    }
}
int main()
{
    //freopen("P2894_5.in","r",stdin);freopen("P2894.out","w",stdout);
    work();
    return 0;
}