记录编号	159533	评测结果	AAAAAAAAAA
题目名称	[HAOI 2013]软件安装	最终得分	100
用户昵称	fyb	是否通过	通过
代码语言	C++	运行时间	0.280 s
提交时间	2015-04-21 18:18:40	内存使用	3.82 MiB

#include <stdio.h>

#define NMAX 50000
#define mid(l,r) (((l)+(r))/2)

struct node{
	int l,r;
	int mxf,lf,rf;
	bool have_lazy,lazy;
};

int pf=0;
node tree[NMAX*2];

int create(int l,int r){
	int tn;

	tn=pf++;
	tree[tn].mxf=tree[tn].lf=tree[tn].rf=r-l+1;
	if(l!=r){
		tree[tn].l=create(l,mid(l,r));
		tree[tn].r=create(mid(l,r)+1,r);
	}
	return tn;
}

void push_down(int tn,int l,int r){
	tree[tree[tn].l].mxf=tree[tree[tn].l].lf=tree[tree[tn].l].rf=(mid(l,r)-l+1)*!(tree[tn].lazy);
	tree[tree[tn].r].mxf=tree[tree[tn].r].lf=tree[tree[tn].r].rf=(r-mid(l,r))*!(tree[tn].lazy);
	tree[tree[tn].l].lazy=tree[tree[tn].r].lazy=tree[tn].lazy;
	tree[tree[tn].l].have_lazy=tree[tree[tn].r].have_lazy=true;
	tree[tn].have_lazy=false;
}

void push_up(int tn,int l,int r){
	if(tree[tree[tn].l].lf>=mid(l,r)-l+1)tree[tn].lf=mid(l,r)-l+1+tree[tree[tn].r].lf;
	else tree[tn].lf=tree[tree[tn].l].lf;
	if(tree[tree[tn].r].rf>=r-mid(l,r))tree[tn].rf=r-mid(l,r)+tree[tree[tn].l].rf;
	else tree[tn].rf=tree[tree[tn].r].rf;
	if(tree[tree[tn].r].mxf>tree[tree[tn].l].mxf)tree[tn].mxf=tree[tree[tn].r].mxf;
	else tree[tn].mxf=tree[tree[tn].l].mxf;
	if(tree[tree[tn].l].rf+tree[tree[tn].r].lf>tree[tn].mxf)tree[tn].mxf=tree[tree[tn].l].rf+tree[tree[tn].r].lf;
	if(tree[tree[tn].l].lf>tree[tn].mxf)tree[tn].mxf=tree[tree[tn].l].lf;
	if(tree[tree[tn].r].rf>tree[tn].mxf)tree[tn].mxf=tree[tree[tn].r].rf;
}

void update(int td,int tm,bool b,int tn,int l,int r){
	if(td<=l&&r<=td+tm-1){
		tree[tn].mxf=tree[tn].lf=tree[tn].rf=(r-l+1)*!b;
		tree[tn].lazy=b;
		tree[tn].have_lazy=true;
	}else{
		if(tree[tn].have_lazy)push_down(tn,l,r);
		if(td<=mid(l,r))update(td,tm,b,tree[tn].l,l,mid(l,r));
		if(td+tm-1>=mid(l,r)+1)update(td,tm,b,tree[tn].r,mid(l,r)+1,r);
		push_up(tn,l,r);
	}
}

int query(int tm,int tn,int l,int r){
	int tmp;

	if(tree[tn].mxf<tm)return 0;
	else{
		if(tree[tn].have_lazy)push_down(tn,l,r);
		if(tmp=query(tm,tree[tn].l,l,mid(l,r)))return tmp;
		else if(tree[tree[tn].l].rf+tree[tree[tn].r].lf>=tm)return mid(l,r)-tree[tree[tn].l].rf+1;
		else return query(tm,tree[tn].r,mid(l,r)+1,r);
	}
}

int main(){
	int n,m;
	int tt,td,tm;
	int i;

	freopen("haoi13t4.in","r",stdin);
	freopen("haoi13t4.out","w",stdout);

	scanf("%d%d",&n,&m);
	getchar();

	create(1,n);

	for(i=0;i<m;i++){
		scanf("%d",&tt);
		if(tt==1){
			scanf("%d",&tm);
			td=query(tm,0,1,n);
			printf("%d\n",td);
			if(td)update(td,tm,true,0,1,n);
		}else{
			scanf("%d%d",&td,&tm);
			update(td,tm,false,0,1,n);
		}
		getchar();
	}
	return 0;
}