本文共 3859 字，大约阅读时间需要 12 分钟。

题目的大致意思是现在有一个宾馆，然后里面共有n个房间，然后有m次询问，每次询问都有两种形式：

1： 那么代表的是现在要搬进来x个人，然后他们是有要求的，他们需要满足他们x个人都是要连续的住在一起，如果没有这种情况的话，那么就输出0，否则输出满足条件的最左边的那个区间；

2： 输入a，b，分别代表的是从a这房间开始，搬出去b个人；

这道题一开始拿到题时并没有什么思路，在网上看了找了许久，找到了两篇比较好的文章（因为大多数都是鱼龙混杂，贴个代码就完事了==b），在这里附上链接，供大家参考。

http://www.2cto.com/kf/201402/278724.html

http://blog.csdn.net/piaoyi0208/article/details/8149804     （我觉得第二篇写的挺好的，因为你可以学习一下他代码中的思路，然后差不多就可以懂了）

思路是：

首先我们设六个标记（有人说只要4个就可以了），分别为l,r（它们代表的是区间），flag（代表的是这个区间是否被标记过，如果为1，说明这个flag所对应的区间已经满了，需要被清空，如果为0，说明flag所对应的区间是空的或者说有人已经搬出去了，如果是-1，当然我们对flag的初始化也是为-1的，就说明不用进行更新操作）。sum（代表的是它所对应的区间含有的房间的总数）。ls与rs（ls代表这个区间从左边开始连续区间的个数，rs代表的是从右边开始连续区间的个数）。

然后我们讲一下pushup这个函数的作用（当然，顾名思义，当然是向上更新的意思），首先当前结点的ls肯定是从左区间中来的，这个画一下图就可以知道了，rs那么是从右区间中来的，然后当当前区间的总ls==mid-tree[v].l+1时，那么就说明我们当前结点的ls还可以扩大的，那么我们还可以加上右儿子的rs，这样就扩大了区间。同理下面一句也是一样的意思。当然，最后，我们还要修改一下tree[v].sum的最大值，它是左右儿子与左儿子的rs加上右儿子的ls中的最大值。

void pushup(int v){	int temp=v<<1;	tree[v].ls=tree[temp].ls;	tree[v].rs=tree[temp+1].rs;	int mid=(tree[v].l+tree[v].r)>>1;	if(tree[v].ls==mid-tree[v].l+1)  tree[v].ls+=tree[temp+1].ls;	if(tree[v].rs==tree[v].r-mid) tree[v].rs+=tree[temp].rs;	tree[v].sum=max(max(tree[temp].sum,tree[temp+1].sum),tree[temp].rs+tree[temp+1].ls);}

然后是pushdown函数，这里是lazy思想的核心，当flag标记不是-1时，那么我们就要往下更新，首先给下面的子节点也都带上flag标记，然后再分类讨论flag的情况，当flag为1的时候，说明已经全都满了，那么要全部清空，要不就是flag为0，说明可以清空了，那么把区间的长度再重新标记为原先的长度。当然最重要的是不要忘记把父节点的flag重新置为-1.

void pushdown(int v){	int temp=v<<1;	if(tree[v].flag!=-1){		tree[temp].flag=tree[temp+1].flag=tree[v].flag;		if(tree[v].flag){			tree[temp].sum=tree[temp].ls=tree[temp].rs=0;			tree[temp+1].sum=tree[temp+1].ls=tree[temp+1].rs=0;		}		else{			tree[temp].sum=tree[temp].ls=tree[temp].rs=tree[temp].r-tree[temp].l+1;			tree[temp+1].sum=tree[temp+1].ls=tree[temp+1].rs=tree[temp+1].r-tree[temp+1].l+1;		}	}	tree[v].flag=-1;}

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;#define maxn 55555int pos=0;struct node{	int l,r,flag;	int sum,ls,rs;}tree[maxn*4];void pushup(int v){	int temp=v<<1;	tree[v].ls=tree[temp].ls;	tree[v].rs=tree[temp+1].rs;	int mid=(tree[v].l+tree[v].r)>>1;	if(tree[v].ls==mid-tree[v].l+1)  tree[v].ls+=tree[temp+1].ls;	if(tree[v].rs==tree[v].r-mid) tree[v].rs+=tree[temp].rs;	tree[v].sum=max(max(tree[temp].sum,tree[temp+1].sum),tree[temp].rs+tree[temp+1].ls);}void pushdown(int v){	int temp=v<<1;	if(tree[v].flag!=-1){		tree[temp].flag=tree[temp+1].flag=tree[v].flag;		if(tree[v].flag){			tree[temp].sum=tree[temp].ls=tree[temp].rs=0;			tree[temp+1].sum=tree[temp+1].ls=tree[temp+1].rs=0;		}		else{			tree[temp].sum=tree[temp].ls=tree[temp].rs=tree[temp].r-tree[temp].l+1;			tree[temp+1].sum=tree[temp+1].ls=tree[temp+1].rs=tree[temp+1].r-tree[temp+1].l+1;		}	}	tree[v].flag=-1;}void build(int l,int r,int v){	tree[v].l=l;	tree[v].r=r;	tree[v].sum=tree[v].ls=tree[v].rs=r-l+1;	tree[v].flag=-1;	if(l==r) return;	int mid=(l+r)>>1;	int temp=v<<1;	build(l,mid,temp);	build(mid+1,r,temp+1);}int query(int l,int r,int v,int x){	if(l==r){		return l;	}	pushdown(v);	int mid=(tree[v].l+tree[v].r)>>1;	int temp=v<<1;	if(tree[temp].sum>=x) return query(l,mid,temp,x);	else if(tree[temp].rs+tree[temp+1].ls>=x) return mid-tree[temp].rs+1;	else return query(mid+1,r,temp+1,x);}void update(int l,int r,int v,int cnt){	if(tree[v].l==l&&r==tree[v].r){		tree[v].flag=cnt;		if(cnt){			tree[v].sum=tree[v].ls=tree[v].rs=0;		}		else{			tree[v].sum=tree[v].ls=tree[v].rs=tree[v].r-tree[v].l+1;		}		return;	}	pushdown(v);	int mid=(tree[v].l+tree[v].r)>>1;	int temp=v<<1;	if(r<=mid) update(l,r,temp,cnt);	else if(l>mid) update(l,r,temp+1,cnt);	else{		update(l,mid,temp,cnt);		update(mid+1,r,temp+1,cnt);	}	pushup(v);}int main(){	int n,m;	int x,q,a,b;	scanf("%d%d",&n,&m);	build(1,n,1);	while(m--){		scanf("%d",&q);		if(q==1){			scanf("%d",&x);			if(tree[1].sum
      
     
    
   

转载地址：https://blog.csdn.net/ACMer_hades/article/details/46537175 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！