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

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;
int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
	return x*f;
}
const int maxn=51000;
int num[maxn*4],lazy[maxn*4],n,m;
int le,ri,hr[maxn*4],hl[maxn*4];
#define lc rt*2
#define rc rt*2+1
void updata(int rt,int l,int r){
	num[rt]=max(num[lc],num[rc]);
	if(hr[lc]&&hl[rc])num[rt]=max(num[rt],hr[lc]+hl[rc]);
	hl[rt]=hl[lc];hr[rt]=hr[rc];
	int mid=(l+r)/2;
	if(num[rc]==r-mid) hr[rt]=num[rc]+hr[lc];
	if(num[lc]==mid-l+1) hl[rt]=num[lc]+hl[rc];
}
void build(int rt,int l,int r){
	lazy[rt]=-1;
	if(l==r){num[rt]=hl[rt]=hr[rt]=1;return;}
	int mid=(l+r)/2;
	build(lc,l,mid);build(rc,mid+1,r);
	updata(rt,l,r);
}
void push_down(int rt,int l,int r){
	if(lazy[rt]==-1)return;
	lazy[lc]=lazy[rc]=lazy[rt];
	int mid=(l+r)/2;
	num[lc]=hl[lc]=hr[lc]=(mid-l+1)*lazy[rt];
	num[rc]=hl[rc]=hr[rc]=(r-mid)*lazy[rt];
	lazy[rt]=-1;
}
void modify(int rt,int l,int r,int x){
	if(le<=l&&ri>=r){
		num[rt]=hl[rt]=hr[rt]=(r-l+1)*x;
		lazy[rt]=x;return;
	}
	push_down(rt,l,r);int mid=(l+r)/2;
	if(le<=mid)modify(lc,l,mid,x);
	if(ri>mid)modify(rc,mid+1,r,x);
	updata(rt,l,r);
}
int query(int rt,int l,int r,int d){
	if(num[rt]<d)return 0;
	if(l==r){
		if(num[rt]==1) return 1;
		else return 0;
	}
	push_down(rt,l,r);int mid=(l+r)/2;
	if(num[lc]>=d)return query(lc,l,mid,d);
	else if(hr[lc]+hl[rc]>=d)return mid-hr[lc]+1;
	else return query(rc,mid+1,r,d);
}
int main(){
	freopen("haoi13t4.in","r",stdin);freopen("haoi13t4.out","w",stdout);
	n=read(),m=read();build(1,1,n);
	for(int i=1,d,x;i<=m;i++){
		int op=read();
		if(op==1){
			d=read(),x=query(1,1,n,d),printf("%d\n",x);
			if(x)le=x,ri=x+d-1,modify(1,1,n,0);
		}	
		else{le=read(),ri=le+read()-1,modify(1,1,n,1);}
	}
	fclose(stdin);fclose(stdout);
	return 0;
}