Hotel 旅馆题解(From luoguBlog)

考试前深陷分块泥潭所以刚开始以为是分块。

然而这题数据水到暴力卡常都能AC

正解：万物皆可线段树

节点存储区间长度、区间最长连续空房长度、从左往右最长连续空房长度、从右往左最长连续空房长度。

维护后三个值即可。

#include<cstdio>

#include<iostream>

#include<cstring>

using namespace std;

int n,m;

const int N=50010;

int read()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

struct node

{

	int maxl,lm,rm,lazy,len;

	#define mid (l+r>>1)

	#define ls (k<<1)

	#define rs (k<<1|1)

	#define maxl(k) tree[k].maxl

	#define lm(k) tree[k].lm

	#define rm(k) tree[k].rm

	#define lazy(k) tree[k].lazy

	#define len(k) tree[k].len

}tree[N<<2];

void up(int k)

{

    lm(k)=(lm(ls)==len(ls))?len(ls)+lm(rs):lm(ls);

    rm(k)=(rm(rs)==len(rs))?len(rs)+rm(ls):rm(rs);

    maxl(k)=max(rm(ls)+lm(rs),max(maxl(ls),maxl(rs)));

}

void downlazy(int k)

{

    if(!lazy(k)) return ;

    lazy(ls)=lazy(rs)=lazy(k);

    maxl(ls)=lm(ls)=rm(ls)=(lazy(k)==1)?len(ls):0;

    maxl(rs)=lm(rs)=rm(rs)=(lazy(k)==1)?len(rs):0;

    lazy(k)=0;

}

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

{

    maxl(k)=lm(k)=rm(k)=len(k)=r-l+1;

    if(l==r) return ;

    build(l,mid,ls);

    build(mid+1,r,rs);

}

void update(int L,int R,int op,int l,int r,int k)

{

    if(L <= l && r <= R){

        maxl(k)=lm(k)=rm(k)=(op==1)?len(k):0;

        lazy(k)=op;

        return ;

    }

    downlazy(k);

    if(L<=mid) update(L,R,op,l,mid,ls);

    if(R>mid) update(L,R,op,mid+1,r,rs);

    up(k);

}

int query(int len,int l,int r,int k)

{

    if(l==r) return l;

    downlazy(k);

    if(maxl(ls)>=len) return query(len,l,mid,ls);

    if(rm(ls)+lm(rs)>=len) return mid-rm(ls)+1;

    return query(len,mid+1,r,rs);

}

int main()

{

	n=read();m=read();

	build(1,n,1);

	int op,x,d;

	while(m--)

	{

		op=read();

		if(op==1)

		{

			d=read();

			if(maxl(1)>=d)

			{

				x=query(d,1,n,1);

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

				update(x,x+d-1,2,1,n,1);

			}

			else puts("0");

		}

		else

		{

			x=read();d=read();

			update(x,x+d-1,1,1,n,1);

		}

	}

	return 0;

}

巴特西

Hotel 旅馆题解(From luoguBlog)

最新文章

热门文章

巴特西

Hotel 旅馆 题解(From luoguBlog)

最新文章

热门文章

Hotel 旅馆题解(From luoguBlog)