自动搬运

查看原文

来自洛谷，原作者为

	Chemist **

搬运于2025-08-24 21:43:09，当前版本为作者最后更新于2018-06-01 19:15:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

区间操作，考虑用线段树维护，需要维护每一段区间的最大连续空房的数量sum，但是只维护这一个值是不够的，因为这时当我们更新节点信息时没法直接让父亲节点的sum等于两个儿子的sum和，比如左儿子在1~4中有三个连续空房1、2、3，右儿子在5~8中有三个连续空房6、7、8，这时父亲的sum显然不等于6而等于3。

因此在新建线段树时需要维护如下信息（懒标记会在下面的区间修改中用到）：

struct Segment_Tree{
	int sum;//区间最大连续空房数
	int len;//区间长度 
	int lmax,rmax;//从左开始或从右开始的最大连续空房数
	int lazy;//懒标记 
}t[4*MAXX];

然后是建树过程，维护上述信息。

void build(int p,int l,int r)
{
	t[p].lazy=0;//懒标记清零
	t[p].sum=t[p].len=t[p].lmax=t[p].rmax=r-l+1;
	//初始均为空房，所以连续空房长度都整个区间长度
	if(l==r)return;
	int mid=(l+r)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r); 
}

懒标记下放：

void spread(int p)
{
	if(t[p].lazy==0)return;
    //没有标记直接返回
	if(t[p].lazy==1){
    //如果要新开房
	    t[p*2].lazy=t[p*2+1].lazy=1;
    //下放懒标记
		t[p*2].sum=t[p*2].lmax=t[p*2].rmax=0;
		t[p*2+1].sum=t[p*2+1].lmax=t[p*2+1].rmax=0;
    //这一段区间没有剩余房间
	}
	if(t[p].lazy==2){
    //如果退房
		t[p*2].lazy=t[p*2+1].lazy=2;
		t[p*2].sum=t[p*2].lmax=t[p*2].rmax=t[p*2].len;
		t[p*2+1].sum=t[p*2+1].lmax=t[p*2+1].rmax=t[p*2+1].len;
    //这一段房间全部是空的
	}
	t[p].lazy=0;//懒标记清零
}

更新节点信息：

void renew(int p)
{
	if(t[p*2].sum==t[p*2].len)//左区间全为空房 
	 t[p].lmax=t[p*2].len+t[p*2+1].lmax;
    //那么左区间全部可住，在加上右区间从左开始的最长区间
	else t[p].lmax=t[p*2].lmax;
    //否则父节点的lmax等于左区间的lmax
	if(t[p*2+1].sum==t[p*2+1].len)//右区间全为空房，同理
	 t[p].rmax=t[p*2+1].len+t[p*2].rmax; 
	else t[p].rmax=t[p*2+1].rmax;
	t[p].sum=max(max(t[p*2].sum,t[p*2+1].sum),t[p*2].rmax+t[p*2+1].lmax);
    //p节点的sum有三种：全在左边的，全在右边的，跨越左右区间的，取个max就好了
} 

现在线段树的基本操作已经完成，再看题，题目要求我们在线段树上支持两种操作：区间修改，查询max(sum)的左端点

区间修改（修改分两种：退房和开房）：

void change(int p,int l,int r,int tag,int L,int R)
//tag=1代表没人住，tag=2代表有人住，[L,R]是要修改的区间 
{
	spread(p);//下放懒标记
	if(L<=l&&r<=R){//如果要修改的区间完全覆盖了当前节点所代表的区间 
    	if(tag==1)t[p].sum=t[p].lmax=t[p].rmax=0;
    //如果要开房，这一段房间全部不可用
		else t[p].sum=t[p].lmax=t[p].rmax=t[p].len; 
    //如果要退房，这一段区间全部可用
		t[p].lazy=tag;//更新懒标记
		return;
	}
	int mid=(l+r)/2;
	if(L<=mid)change(p*2,l,mid,tag,L,R);
	if(R>mid)change(p*2+1,mid+1,r,tag,L,R);
    //修改左右儿子
	renew(p);//更新节点信息
}

查询：

int ask(int p,int l,int r,int length)
{
	spread(p);//下放懒标记
	if(l==r)return l;//如果找到对应区间，返回左端点
	int mid=(l+r)/2;
	if(t[p*2].sum>=length)return ask(p*2,l,mid,length);
    //如果左区间即可找到足够多的房间，就在左区间找
	if(t[p*2].rmax+t[p*2+1].lmax>=length)return mid-t[p*2].rmax+1;
    //如果在中间能找到足够多的房间，答案就是左区间从右开始的最长连续区间的左端点
	else return ask(p*2+1,mid+1,r,length);
    //否则就在右边找
}

最后的主函数：

int main()
{
	n=read();m=read();
	build(1,1,n);//建树
	for(int i=1;i<=m;i++) 
	{
		int act,x,y;
		act=read();
		if(act==1){
			x=read();
			if(t[1].sum>=x){
        //如果存在这么长的区间才找
				int left=ask(1,1,n,x);
				printf("%d\n",left);
				change(1,1,n,1,left,left+x-1);
                //找到之后记得修改
			}
			else printf("0\n");//否则找不到
		}
		else{
			x=read();y=read();
			change(1,1,n,2,x,x+y-1);//退房	
		}
	}
	return 0;
}