记录编号	141976	评测结果	AAAAAAAAAA
题目名称	[HAOI 2013]软件安装	最终得分	100
用户昵称	TA	是否通过	通过
代码语言	C++	运行时间	0.115 s
提交时间	2014-12-05 20:00:48	内存使用	14.43 MiB

#include<iostream>
using namespace std;
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define root 1,1,N
#define lson node<<1,l,(l+r)>>1
#define rson node<<1|1,((l+r)>>1)+1,r
struct S{
	int max,lmax,lR,rmax,rL;
}tree[200000];
int flag[200000];
char * ptr=(char *)malloc(10000000);
inline void in(int &x){
	while(*ptr<'0'||*ptr>'9')++ptr;
	x=0;
	while(*ptr>47&&*ptr<58)x=x*10+*ptr++-'0';
}
inline void paint(int node,int l,int r,int x){
	if(x)tree[node]=(S){r-l+1,r-l+1,r,r-l+1,l};
	else tree[node]=(S){0,0,l-1,0,r+1};
}
inline void out(int node,int l,int r){
	cout<<l<<","<<r<<":"<<tree[node].max<<" "<<tree[node].lmax<<"("<<tree[node].lR<<")"<<" "<<tree[node].rmax<<"("<<tree[node].rL<<")\n";
}
inline void build(int node,int l,int r){
	paint(node,l,r,1);
	if(l!=r)build(lson),build(rson);
}
inline void pushdown(int node,int l,int r){
	paint(node<<1,l,(l+r)>>1,flag[node]);
	paint(node<<1|1,((l+r)>>1)+1,r,flag[node]);
	flag[node<<1]=flag[node<<1|1]=flag[node];
	flag[node]=-1;
}
inline int query(int node,int l,int r,int len){
	//cout<<"Q:",out(node,l,r);
	if(l==r)return l;
	if(flag[node]+1)pushdown(node,l,r);
	if(tree[node<<1].max>=len)return query(lson,len);
	if(tree[node<<1].rmax+tree[node<<1|1].lmax>=len)return tree[node<<1].rL;
	return query(rson,len);
}
inline void update(int node,int l,int r,int a,int b,int x){
	if(a<=l&&r<=b){
		paint(node,l,r,x);
		flag[node]=x;
		//cout<<"U:",out(node,l,r);
		return;
	}
	if(a>r||b<l)return;
	if(flag[node]+1)pushdown(node,l,r);
	update(lson,a,b,x);
	update(rson,a,b,x);
	tree[node].max=max(tree[node<<1].max,max(tree[node<<1|1].max,tree[node<<1].rmax+tree[node<<1|1].lmax));
	if(tree[node<<1].lmax==((l+r)>>1)-l+1){
		tree[node].lmax=tree[node<<1].lmax+tree[node<<1|1].lmax;
		tree[node].lR=tree[node<<1|1].lR;
	}
	else{
		tree[node].lmax=tree[node<<1].lmax;
		tree[node].lR=tree[node<<1].lR;
	}
	if(tree[node<<1|1].rmax==r-((l+r)>>1)){
		tree[node].rmax=tree[node<<1].rmax+tree[node<<1|1].rmax;
		tree[node].rL=tree[node<<1].rL;
	}
	else{
		tree[node].rmax=tree[node<<1|1].rmax;
		tree[node].rL=tree[node<<1|1].rL;
	}
	//cout<<"U:",out(node,l,r);
}
int main(){
	freopen("haoi13t4.in","r",stdin);
	freopen("haoi13t4.out","w",stdout);
	fread(ptr,1,10000000,stdin);
	int N,M;
	in(N),in(M);
	build(root);
	memset(flag,-1,sizeof(flag));
	int flag,len,l;
	while(M--){
		in(flag);
		if(flag-1){
			in(l),in(len);
			update(root,l,l+len-1,1);
		}
		else{
			in(len);
			if(tree[1].max>=len){
				printf("%d\n",l=query(root,len));
				update(root,l,l+len-1,0);
			}
			else printf("0\n");
		}
	}
}