记录编号	333807	评测结果	AAAAAAAAAA
题目名称	[HAOI 2013]软件安装	最终得分	100
用户昵称	NewBee	是否通过	通过
代码语言	C++	运行时间	0.288 s
提交时间	2016-10-31 15:19:06	内存使用	2.83 MiB

#include<cstdio>
#define Cu fclose(stdin);fclose(stdout);return 0;
#define Begin freopen("haoi13t4.in","r",stdin);freopen("haoi13t4.out","w",stdout);chul();Cu;
using namespace std;
const int maxn=50010;
int n,pre[maxn<<2],nex[maxn<<2],minl,tot[maxn<<2],s,t;
bool roo[maxn<<2];
short lazy[maxn<<2];
int min(int x,int y){
	if(x>y)return y;
	return x;
}
int max(int x,int y){
	if(x>y)return x;
	return y;
}
void build(int rt,int l,int r){
	if(l==r){
		lazy[rt]=roo[rt]=0;
		pre[rt]=nex[rt]=tot[rt]=1;
		return;
	}
	int mid=(l+r)>>1;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
	pre[rt]=nex[rt]=tot[rt]=r-l+1;
}	
void update(int rt,int l,int mid,int r){
	if(lazy[rt]==0)return;
	int k=lazy[rt];
	lazy[rt]=0;
	if(k==1){
		roo[rt<<1]=1;
		lazy[rt<<1]=1;
		nex[rt<<1]=pre[rt<<1]=tot[rt<<1]=0;
		roo[rt<<1|1]=1;
		lazy[rt<<1|1]=1;
		nex[rt<<1|1]=pre[rt<<1|1]=tot[rt<<1|1]=0;
	}
	else{
		roo[rt<<1]=0;
		lazy[rt<<1]=2;
		nex[rt<<1]=pre[rt<<1]=tot[rt<<1]=mid-l+1;
		roo[rt<<1|1]=0;
		lazy[rt<<1|1]=2;
		nex[rt<<1|1]=pre[rt<<1|1]=tot[rt<<1|1]=r-mid;
	}
}
void asks(int rt,int l,int r,int d,bool k){
	if(!roo[rt]&&r-l+1==d){
		roo[rt]=1;
		lazy[rt]=1;
		minl=min(minl,l);
		pre[rt]=nex[rt]=tot[rt]=0;
		return;
	}
	int mid=(l+r)>>1;
	update(rt,l,mid,r);
	if(k==0){
		if(tot[rt<<1]>=d)asks(rt<<1,l,mid,d,0);
		else if(nex[rt<<1]!=0&&nex[rt<<1]+pre[rt<<1|1]>=d){
			int mmm=d-nex[rt<<1];
			asks(rt<<1,l,mid,nex[rt<<1],1);
			asks(rt<<1|1,mid+1,r,mmm,0);
		}
		else asks(rt<<1|1,mid+1,r,d,0);
	}
	else{
		if(tot[rt<<1|1]>=d)asks(rt<<1|1,mid+1,r,d,1);
		else {
			int mmm=d-pre[rt<<1|1];
			asks(rt<<1|1,mid+1,r,pre[rt<<1|1],1);
			asks(rt<<1,l,mid,mmm,1);
		}
	}
	pre[rt]=pre[rt<<1];
	if(!roo[rt<<1])pre[rt]=max(pre[rt],pre[rt<<1|1]+tot[rt<<1]);
	nex[rt]=nex[rt<<1|1];
	if(!roo[rt<<1|1]){
		nex[rt]=max(nex[rt],nex[rt<<1]+tot[rt<<1|1]);
	}
	tot[rt]=max(nex[rt<<1]+pre[rt<<1|1],max(tot[rt<<1],tot[rt<<1|1]));
	roo[rt]=roo[rt<<1]|roo[rt<<1|1];
}
void inho(){
	int d;
	scanf("%d",&d);
	if(tot[1]<d){
		printf("0\n");
		return;
	}
	minl=n+1;
	asks(1,1,n,d,0);
	printf("%d\n",minl);
}
void outhot(int rt,int l,int r){
	if(s<=l&&t>=r){
		lazy[rt]=2;
		roo[rt]=0;
		pre[rt]=nex[rt]=tot[rt]=r-l+1;
		return;
	}
	int mid=(l+r)>>1;
	update(rt,l,mid,r);
	if(s<=mid)outhot(rt<<1,l,mid);
	if(t>mid)outhot(rt<<1|1,mid+1,r);
	pre[rt]=pre[rt<<1];
	if(!roo[rt<<1])pre[rt]=max(pre[rt],pre[rt<<1|1]+tot[rt<<1]);
	nex[rt]=nex[rt<<1|1];
	if(!roo[rt<<1|1]){
		nex[rt]=max(nex[rt],nex[rt<<1]+tot[rt<<1|1]);
	}
	tot[rt]=max(nex[rt<<1]+pre[rt<<1|1],max(tot[rt<<1],tot[rt<<1|1]));
	roo[rt]=roo[rt<<1]|roo[rt<<1|1];
}
void outho(){
	scanf("%d%d",&s,&t);
	t=s+t-1;
	outhot(1,1,n);
}
void chul(){
	int m;
	scanf("%d%d",&n,&m);
	build(1,1,n);
	int k;
	for(int i=1;i<=m;i++){
		scanf("%d",&k);
		if(k==1)inho();
		else outho();
	}
}
int main(){
	Begin;
	chul();
}