C++14(g++5.4) 解法, 执行用时: 61ms, 内存消耗: 4584K, 提交时间: 2020-04-24 00:26:57

/*
	题目大意：
	n个房间，初始为空 
	m次询问，2种类型
	1 d 要连续分配d个房间，给出满足条件的最小起始编号 ，如果不能满足输出0 
	2 x d 退房，从x开始连续退掉d个房间，房间原来可能是空的 
	
	需要维护最大0区间 ，类似维护最大连续子段和的思路 
*/ 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; 
struct SegmentTree{
	ll l,r,sum,tag;//l是紧靠左边的最大零区间的长度，r是紧靠右边的最大零区间的长度，sum最大零区间的长度，tag延迟标记 ，记录取反的次数 
	#define l(x) tree[x].l
	#define r(x) tree[x].r
	#define sum(x) tree[x].sum
	#define tag(x) tree[x].tag
}tree[50010*4];
ll n,m,x,d,f;
void push_up(int p,int l,int r)
{
	int mid=(l+r)/2;
	l(p)=(l(p*2)==mid-l+1)?l(p*2)+l(p*2+1):l(p*2);//如果左子节点紧靠左边的最大零区间的长度是节点全部，那么该节点的紧靠左边的最大零区间长度就是l(p*2)+l(p*2+1) 
	r(p)=(r(p*2+1)==r-mid)?r(p*2+1)+r(p*2):r(p*2+1);
	sum(p)=max(max(sum(p*2),sum(p*2+1)),r(p*2)+l(p*2+1)); 
}
void push_down(int p,int l,int r)//向下传递标记
{
	if(tag(p)==1)
	{
		tag(p*2)=tag(p*2+1)=1;
		l(p*2)=r(p*2)=sum(p*2)=0;
		l(p*2+1)=r(p*2+1)=sum(p*2+1)=0;
	}
	if(tag(p)==2)
	{
		tag(p*2)=tag(p*2+1)=2;
		int mid=(l+r)/2;
		l(p*2)=r(p*2)=sum(p*2)=mid-l+1;
		l(p*2+1)=r(p*2+1)=sum(p*2+1)=r-mid;
	}
	tag(p)=0;
} 
void build(int p,int l,int r)
{
	if(l==r){l(p)=r(p)=sum(p)=1;return ;} //叶子节点
	int mid=(l+r)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	push_up(p,l,r);
}
void change(int p,int L,int R,int l,int r,int v)
{
	if(L<=l and r<=R)
	{
		if(v==1)//check in 
		{
			tag(p)=1;
			l(p)=r(p)=sum(p)=0;
		}
		else//check out 
		{
			tag(p)=2;
			l(p)=r(p)=sum(p)=r-l+1;
		}
		return ;
	}
	push_down(p,l,r);
	int mid=(l+r)/2;
	if(L<=mid)change(p*2,L,R,l,mid,v);
	if(mid<R)change(p*2+1,L,R,mid+1,r,v);
	push_up(p,l,r);
}
int ask(int p,int l,int r,int sum)
{
	if(l==r)return l;
	push_down(p,l,r);
	int mid=(l+r)/2;
	if(sum(p*2)>=sum)return ask(p*2,l,mid,sum);//在左边找
	else if(r(p*2)+l(p*2+1)>=sum)return mid-r(p*2)+1;
	else return ask(p*2+1,mid+1,r,sum); 
}
int main()
{
	scanf("%ld%ld",&n,&m);
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		scanf("%ld",&f);
		if(f==1)
		{
			scanf("%ld",&d);
			if(sum(1)<d)puts("0");
			else
			{
				int pos=ask(1,1,n,d);
				change(1,pos,pos+d-1,1,n,1);
				printf("%d\n",pos);
			}
		}
		else
		{
			scanf("%ld%ld",&x,&d);
			change(1,x,x+d-1,1,n,2);	
		}
	}
} 

C++(g++ 7.5.0) 解法, 执行用时: 48ms, 内存消耗: 3604K, 提交时间: 2022-08-09 10:16:37

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int sum,lsum,rsum;
	int left,right;
	int lazy;
}a[200100];
int n,m;
void update(int k)
{
	a[k].lsum=a[k<<1].lsum;
	a[k].rsum=a[k<<1|1].rsum;
	if(a[k<<1].sum==a[k<<1].right-a[k<<1].left+1)
        a[k].lsum+=a[k<<1|1].lsum;
	if(a[k<<1|1].sum==a[k<<1|1].right-a[k<<1|1].left+1)
        a[k].rsum+=a[k<<1].rsum;
	a[k].sum=max(a[k<<1].rsum+a[k<<1|1].lsum,max(a[k<<1].sum,a[k<<1|1].sum));
	return ;
}
void pushdown(int k)
{
	if(a[k].lazy==-1) return;
	a[k<<1].lsum=a[k<<1].rsum=a[k<<1].sum=(a[k<<1].right-a[k<<1].left+1)*a[k].lazy;
	a[k<<1|1].lsum=a[k<<1|1].rsum=a[k<<1|1].sum=(a[k<<1|1].right-a[k<<1|1].left+1)*a[k].lazy;
	a[k<<1|1].lazy=a[k<<1].lazy=a[k].lazy;
	a[k].lazy=-1;
	return ;
}
void build(int k,int left,int right)
{
	a[k].left=left,a[k].right=right;
	a[k].lsum=a[k].rsum=a[k].sum=right-left+1;
    a[k].lazy=-1;
	if(left==right) return ;
	int mid=(left+right)>>1;
	build(k<<1,left,mid);
	build(k<<1|1,mid+1,right);
	return ;
}
void change(int k,int left,int right,int x)
{
	if(left<=a[k].left&&a[k].right<=right)
	{
		a[k].lazy=x;
		a[k].sum=a[k].lsum=a[k].rsum=(a[k].right-a[k].left+1)*x;
		return ;
	}
	pushdown(k);
	int mid=(a[k].left+a[k].right)>>1;
	if(left<=mid) change(k<<1,left,right,x);
	if(mid<right) change(k<<1|1,left,right,x);
	update(k);
	return ;
}
int query(int k,int x)
{
	if(a[k].left==a[k].right) return a[k].left;
	pushdown(k);
	if(a[k<<1].sum>=x) return query(k<<1,x);
	else if(a[k<<1].rsum+a[k<<1|1].lsum>=x) return a[k<<1].right-a[k<<1].rsum+1;
	else return query(k<<1|1,x);
}
int main()
{
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		build(1,1,n);
		while(m--)
		{
			int c;
			scanf("%d",&c);
			if(c==1)
			{
				int x;
				scanf("%d",&x);
				if(x>a[1].sum) printf("0\n");
				else
				{
					int ans=query(1,x);
					printf("%d\n",ans);
					change(1,ans,ans+x-1,0);
				}
			}
			else
			{
				int x,y;
				scanf("%d%d",&x,&y);
				change(1,x,x+y-1,1);
			}
		}
	}
	return 0;
}

C++ 解法, 执行用时: 167ms, 内存消耗: 3064K, 提交时间: 2022-05-02 09:50:41

#include<bits/stdc++.h>
using namespace std;
int n,m,x,l,op;
struct node{
	int ss,lm,rm,ll,len;
	#define mid (l+r>>1)
	#define lss (rt<<1)
	#define rss (rt<<1|1)
	#define ss(rt) te[rt].ss
	#define lm(rt) te[rt].lm
	#define rm(rt) te[rt].rm
	#define ll(rt) te[rt].ll
	#define len(rt) te[rt].len
}te[2000001];
void pu(int rt){
	lm(rt)=(lm(lss)==len(lss))?len(lss)+lm(rss):lm(lss);
	rm(rt)=(rm(rss)==len(rss))?len(rss)+rm(lss):rm(rss);
	ss(rt)=max(rm(lss)+lm(rss),max(ss(lss),ss(rss)));
}
void pd(int rt){
	if(!ll(rt))return;
	ll(lss)=ll(rss)=ll(rt);
	ss(lss)=lm(lss)=rm(lss)=(ll(rt)==1)?len(lss):0;
	ss(rss)=lm(rss)=rm(rss)=(ll(rt)==1)?len(rss):0;
	ll(rt)=0;
}
void bd(int l,int r,int rt){ss(rt)=lm(rt)=rm(rt)=len(rt)=r-l+1;if(l==r)return;bd(l,mid,lss);bd(mid+1,r,rss);}
void update(int L,int R,int tag,int l,int r,int rt){
	if(L<=l&&r<=R){ss(rt)=lm(rt)=rm(rt)=(tag==1)?len(rt):0;ll(rt)=tag;return;}
	pd(rt);
	if(L<=mid)update(L,R,tag,l,mid,lss);
	if(R>mid)update(L,R,tag,mid+1,r,rss);
	pu(rt);
}
int qr(int len,int l,int r,int rt){
	if(l==r)return l;
	pd(rt);
	if(ss(lss)>=len)return qr(len,l,mid,lss);
	if(rm(lss)+lm(rss)>=len)return mid-rm(lss)+1;
	return qr(len,mid+1,r,rss);
}
int main(){
	cin>>n>>m;
	bd(1,n,1);
	while(m--){
		cin>>op;
		if(op==1){
			cin>>x;
			if(ss(1)>=x)l=qr(x,1,n,1),cout<<l<<"\n",update(l,l+x-1,2,1,n,1);
			else cout<<"0\n";
		}
		else cin>>l>>x,update(l,l+x-1,1,1,n,1);
	}
	return 0;
}