POJ3667 Hotel 题解

和最大子段和的思路是一样的，可以记 \(lmax,rmax,dat\) 分别表示从当前区间最靠左/右的最大连续空子段和当前区间的最大连续空子段。

需要用延迟标记，每次遇到开房操作先ask，如果能找到就修改这一段。

注意更新节点时要讨论左/右区间是否全部空/非空。

#include <cstdio>

#include <algorithm>

using namespace std;

const int N=5e4;

struct Edge

{

    int l,r,dat,lmax,rmax,tag;

    #define l(x) t[x].l

    #define r(x) t[x].r

    #define tag(x) t[x].tag

    #define len(x) (t[x].r-t[x].l+1)

}t[(N<<2)+5];

int n,m;

void build(int rt,int l,int r)

{

    l(rt)=l,r(rt)=r;

    t[rt].dat=t[rt].lmax=t[rt].rmax=r-l+1;

    if(l==r) return;

    int mid=l+r>>1;

    build(rt<<1,l,mid);

    build(rt<<1|1,mid+1,r);

}

inline void pushdown(int rt)

{

    if(!tag(rt)) return;

    tag(rt<<1)=tag(rt<<1|1)=tag(rt);

    t[rt<<1].dat=t[rt<<1].lmax=t[rt<<1].rmax=tag(rt)==1?0:len(rt<<1);

    t[rt<<1|1].dat=t[rt<<1|1].lmax=t[rt<<1|1].rmax=tag(rt)==1?0:len(rt<<1|1);

    tag(rt)=0;

}

int ask(int rt,int x)

{

    pushdown(rt);

    if(l(rt)==r(rt)) return l(rt);

    if(t[rt<<1].dat>=x) return ask(rt<<1,x);

    int mid=l(rt)+r(rt)>>1;

    if(t[rt<<1].rmax+t[rt<<1|1].lmax>=x) return mid-t[rt<<1].rmax+1;

    return ask(rt<<1|1,x);

}

void change(int rt,int l,int r,int tag)

{

    if(l<=l(rt)&&r>=r(rt))

	{

		t[rt].dat=t[rt].lmax=t[rt].rmax=tag==1?0:len(rt);

		tag(rt)=tag; return;

	}

    pushdown(rt);

    int mid=l(rt)+r(rt)>>1;

    if(l<=mid) change(rt<<1,l,r,tag);

    if(r>mid) change(rt<<1|1,l,r,tag);

    if(t[rt<<1].dat==len(rt<<1))

        t[rt].lmax=len(rt<<1)+t[rt<<1|1].lmax;

    else t[rt].lmax=t[rt<<1].lmax;

    if(t[rt<<1|1].dat==len(rt<<1|1))

        t[rt].rmax=len(rt<<1|1)+t[rt<<1].rmax;

    else t[rt].rmax=t[rt<<1|1].rmax;

    t[rt].dat=max(max(t[rt<<1].dat,t[rt<<1|1].dat),t[rt<<1].rmax+t[rt<<1|1].lmax);

}

int main()

{

    scanf("%d%d",&n,&m);

    build(1,1,n);

    for(int i=1,op;i<=m;++i)

    {

        scanf("%d",&op);

        if(op==1)

        {

            int x; scanf("%d",&x);

            if(t[1].dat>=x)

            {

                int l=ask(1,x);

                printf("%d\n",l);

                change(1,l,l+x-1,1);

            }

            else puts("0");

        }

        else

        {

            int l,x; scanf("%d%d",&l,&x);

            change(1,l,l+x-1,2);

        }

    }

    return 0;

}

巴特西

POJ3667 Hotel 题解

最新文章

热门文章