记录编号	360606	评测结果	AAAAAAAAAA
题目名称	[HAOI 2013]软件安装	最终得分	100
用户昵称	Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.164 s
提交时间	2016-12-30 17:49:17	内存使用	3.38 MiB

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define Inf 2e9
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
const int maxn=50000+200;
struct Node{
	int max,ls,rs,lazy;
}a[maxn<<2];
int n,m;
void Build(int rt,int l,int r){
	a[rt].lazy=-1;
	a[rt].max=a[rt].ls=a[rt].rs=r-l+1;
	if(l==r)return;
	int mid=(l+r)>>1;
	Build(lson);Build(rson); 
}
void Update(int rt,int l,int r){
	int z=a[rt].lazy;a[rt].lazy=-1;
	a[rt<<1].lazy=a[rt<<1|1].lazy=z;
	int mid=(l+r)>>1;
	a[rt<<1].max=a[rt<<1].ls=a[rt<<1].rs=(mid-l+1)*z;
	a[rt<<1|1].max=a[rt<<1|1].ls=a[rt<<1|1].rs=(r-mid)*z;
}
void pushup(int rt,int l,int r){
	a[rt].max=max(a[rt<<1].max,a[rt<<1|1].max);
	a[rt].max=max(a[rt].max,a[rt<<1].rs+a[rt<<1|1].ls);
	int mid=(l+r)>>1;
	if(a[rt<<1].max==mid-l+1)a[rt].ls=mid-l+1+a[rt<<1|1].ls;
	else a[rt].ls=a[rt<<1].ls;
	if(a[rt<<1|1].max==r-mid)a[rt].rs=r-mid+a[rt<<1].rs;
	else a[rt].rs=a[rt<<1|1].rs;
}
void Insert(int s,int t,int z,int rt,int l,int r){
	if(s<=l && t>=r){
		a[rt].lazy=z;
		a[rt].max=a[rt].ls=a[rt].rs=z*(r-l+1);
		return;
	}
	if(a[rt].lazy!=-1)Update(rt,l,r);
	int mid=(l+r)>>1;
	if(s<=mid)Insert(s,t,z,lson);
	if(t>mid)Insert(s,t,z,rson);
	pushup(rt,l,r);
}
int Get_boundary(int z,int rt,int l,int r){
	if(a[rt].max==z && a[rt].ls==z)return l;
	if(a[rt].lazy!=-1)Update(rt,l,r);
	int mid=(l+r)>>1;
	if(a[rt<<1].max>=z)return Get_boundary(z,lson);
	if(a[rt<<1].rs+a[rt<<1|1].ls>=z)return mid-a[rt<<1].rs+1;
	if(a[rt<<1|1].max>=z)return Get_boundary(z,rson);
	pushup(rt,l,r);
}
void Init();
int main(){
    freopen("haoi13t4.in","r",stdin);freopen("haoi13t4.out","w",stdout);
    Init();
    getchar();getchar();
    return 0;
}
void Init(){
	scanf("%d%d",&n,&m);
	Build(1,1,n);
	for(int i=1;i<=m;i++){
		int type,L,date;scanf("%d",&type);
		if(type==1){
			scanf("%d",&date);
			if(a[1].max<date){puts("0");continue;}
			L=Get_boundary(date,1,1,n);
			printf("%d\n",L);
			Insert(L,L+date-1,false,1,1,n);
		}
		else {
			scanf("%d%d",&L,&date);
			Insert(L,L+date-1,true,1,1,n);
		}
		//printf("max=%d\n",a[1].max);
	}
}