2128 - 【USACO2008FEB】酒店

C++解答

#include<cstdio>
#define kl k<<1
#define kr k<<1|1
const int N=50001;
int f[N<<2];
struct node{int sr,sl,ms;}t[N<<2];
int max(int a,int b){if(a>b)return a;return b;}
void build(int L,int R,int k){
	t[k].sl=t[k].sr=t[k].ms=R-L+1;
	if(L==R)return;
	int mid=(L+R)>>1;
	build(L,mid,kl);
	build(mid+1,R,kr);
}
void pushdown(int k,int L,int R){
	if(f[k]!=0){
		f[kl]=f[kr]=f[k];
		t[kl].sl=t[kl].sr=t[kl].ms=f[k]==1?R-L+1:0;
		t[kr].sl=t[kr].sr=t[kl].ms=f[k]==1?R-L+1:0;
		f[k]=0;
	}
}
void pushup(int k,int d){
	t[k].sl=t[kl].sl;
	t[k].sr=t[kr].sr;
	if(t[kl].sl==d-(d>>1))t[k].sl+=t[kr].sl;
	if(t[kr].sr==d>>1)t[k].sr+=t[kl].sr;
	t[k].ms=max(max(t[kl].ms,t[kr].ms),t[kl].sr+t[kr].sl);
}
int query(int L,int R,int x,int k){
	if(L==R)return L;
	pushdown(k,L,R);
	int mid=(L+R)>>1;
	if(t[kl].ms>=x)return query(L,mid,x,kl);
	else if(t[kl].sr+t[kr].sl>=x)return mid-t[kl].sr+1;
	return query(mid+1,R,x,kr);
}
void update(int L,int R,int s,int e,int c,int k){
	if(s<=L&&e>=R){
		t[k].sl=t[k].sr=t[k].ms=c==1?R-L+1:0;
		f[k]=c;
		return;
	}
	pushdown(k,L,R);
	int mid=(L+R)>>1;
	if(s<=mid)update(L,mid,s,e,c,kl);
	if(e>mid)update(mid+1,R,s,e,c,kr);
	pushup(k,R-L+1);
}
int main(){
	int i,n,m,a,b,c;
	scanf("%d%d",&n,&m);
	build(1,n,1);
	for(i=0;i<m;i++){
		scanf("%d",&c);
		if(c==1){
			scanf("%d",&a);
			if(t[1].ms<a)printf("0\n");
			else printf("%d\n",b=query(1,n,b,1)),update(1,n,b,b+a-1,-1,1);
		}
		else scanf("%d%d",&a,&b),update(1,n,a,a+b-1,1,1);
	}
	return 0;
}