题目大意：就是一个man从 最高处的横木往下跳，在这里与我们平时的游戏有点出入，在此处 我们只能往最近的，并且包含我左或右端点的一个横木区间上跳。man的初始血量为100，每跳到一个横木上他的血量都有可能发生变化，当横木上放着食物的时候，man的血回increase，如果是障碍之类的就损耗血量。

题目分析：在这里我们要处理的问题只有两个：1）如何才能找到包含当前区间的左，右端点的最近 的区间  2）如何跳才能剩下最多血量到达地面。

解决方案：首先按横木高度 进行升序排序，然后从低往高 进行插入，并且 查询包含其左或者右端点的 最近的 下面的区间：查找每块木板左边和右边的木板时只需要在线段树上找左边和右边坐标被谁覆盖就好了；

然后就是选择最优的操作方案：dp方程：dp[left]=max(dp[left],dp[i]+w[left]);  在这里详细的解释一下各个变量的 实际意义：dp[left]是指没有经过第i块横木 跳下来的的方案的血量，dp[i]表示跳到第i个横木所剩下的血，w[left]是指left这个横木上所消耗的血，dp[i]+w[left]是指经过第i个横木然后跳到left上的方案，dp方程就是为了 在这两大类方案中选择最优的！！

代码如下：

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<algorithm>
using namespace std;

struct TREE{
	int a,b;
	int color;
}tree[300000];

struct node{
	int x,y,h;
	int left,right,w;
}s[300000];

int dp[100000];

int cmp(struct node a,struct node b){
	return a.h<b.h;
}

int Build(int x,int y,int num){
	tree[num].a=x;	tree[num].b=y;
	tree[num].color=0;
	if(x==y)
		return 0;
	int mid=(x+y)/2;
	Build(x,mid,num+num);
	Build(mid+1,y,num+num+1);
}

int modify(int x,int y,int num,int flag){
	if(x<=tree[num].a&&y>=tree[num].b){
		tree[num].color=flag;
		return 0;
	}
	if(tree[num].color!=-1){
		tree[num+num+1].color=tree[num+num].color=tree[num].color;
		tree[num].color=-1;
	}
	int mid=(tree[num].a+tree[num].b)/2;
	if(x<=mid)
		modify(x,y,num+num,flag);
	if(y>=mid+1)
		modify(x,y,num+num+1,flag);
}

int search(int pos,int num){
	if(tree[num].color!=-1)
		return tree[num].color;
	int mid=(tree[num].a+tree[num].b)/2;
	if(pos<=mid)
		search(pos,num+num);
	else if(pos>=mid+1)
		search(pos,num+num+1);
}

int main(){
	int i,n,maxn;
	Build(1,100000,1);
	while(scanf("%d",&n)!=EOF){
		maxn=0;
		memset(dp,0,sizeof(dp));
		for(i=1;i<=n;i++){
			scanf("%d %d %d %d",&s[i].h,&s[i].x,&s[i].y,&s[i].w);
			if(maxn<s[i].y)
				maxn=s[i].y;
		}
		modify(1,maxn,1,0);
		sort(s+1,s+1+n,cmp);
		for(i=1;i<=n;i++){
			s[i].left=search(s[i].x,1);
			s[i].right=search(s[i].y,1);
			modify(s[i].x,s[i].y,1,i);
		}
		dp[n]=100+s[n].w;
		for(i=n;i>=0;i--){
			if(dp[i]>0){//在这里如果dp[i]小于等于0就是说经过i块横木是不明智的选择，就直接忽略掉了！！
				dp[s[i].left]=max(dp[s[i].left],dp[i]+s[s[i].left].w);
				dp[s[i].right]=max(dp[s[i].right],dp[i]+s[s[i].right].w);
			}
		}
		if(dp[0]>0)
			printf("%d\n",dp[0]);
		else
			printf("-1\n");
	}
	return 0;
}

题目分析：在一个很长的节点序列上（长度最大可以到2^31）,如果建树，则离散不了各个节点，因为求的是长度区间，在次我们换向考虑一下，原始是黑色的 各个节点，我们只需考虑对白色节点进行染黑的操作，其他的都不需要考虑，把各个连续的白色节点区间存储在节点数组里面，然后当遇到要进行染黑操作时，直接在白色区间数组里分个进行讨论，没个区间枚举四种不同情况，相应的维护区间。

最后就是在计算最长去区间 的时候稍微要点技巧：1）首先考虑前后是否可以合并，2）保存目前最大值，与最大值的区间端点。

代码如下：

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
using namespace std;

struct node{
	int beg,en;
}s[8000];

int cmp(struct node a,struct node b){
	if(a.beg!=b.beg){
		return a.beg<b.beg;
	}
	else 
		return a.en>b.en;
}

int main(){
	int n,beg,en,sn,tn;
	int Max,x,y,len,i;
	char c;
	while(scanf("%d",&n)!=EOF){
		memset(s,0,sizeof(s));//每次个案例都要初始化哦，请您注意一下
		len=0;
		while(n--){
			scanf("%d %d %c",&beg,&en,&c);
			if(c=='w'){
				s[len].beg=beg;
				s[len].en=en;
				len++;			
			}
			else{
				for(i=0;i<len;i++){
					if(beg<=s[i].beg&&en>=s[i].en)
						s[i].beg=s[i].en=-1;
					else if(beg<=s[i].beg&&en<=s[i].en&&en>=s[i].beg)
						s[i].beg=en+1;
					else if(beg>=s[i].beg&&en<=s[i].en){
						s[len].en=s[i].en;
						s[i].en=beg-1;
						s[len].beg=en+1;
						len++;
					}
					else if(beg>=s[i].beg&&en>=s[i].en&&beg<=s[i].en)
						s[i].en=beg-1;
				}
			}
		}
		Max=x=y=-1;
		sort(s,s+len,cmp);
		//for(i=0;i<len;i++)
			//cout<<s[i].beg<<" "<<s[i].en<<endl;
		for(i=0;i<len;i++){
			if(s[i].beg!=-1){
				if(s[i].beg<=y+1)
					y=max(s[i].en,y);
				else {
					x=s[i].beg;	y=s[i].en;				
				}
				if(Max<y-x+1){
					Max=y-x+1;
					sn=x;	tn=y;		
				}
			}
		}
		if(Max==-1)
			printf("Oh, my god\n");
        	else
            		printf("%d %d\n",sn,tn);
	}
	return 0;
}

题目分析：题目有4个操作：Reset指清空整个线段树，即题目所说的清空整个内存块；New N就是申请N个最靠左边的连续内存块，Free x操作是释放包含x的连续内存块，Get x，就是获得第x个内存块的起始节点，如果不深刻去体会，也许会认为要改造serch函数，其实仔细看看，事实是这样的：这里的建树，查询，更新都是与经典类型HOTEL里的一样的，如果不懂您可以看一下我另外一片博客，在这里我们已经解决了，1）查找包含x的区间的起始位置，2）申请一个长度为N的最靠左的连续区间，返回起点。然后我们会发挥已经解决的问题，我们用vector存取所有申请过的空间，删除所有释放的空间，查询第n个区间也是非常easy。关键在于vector可以在中间进行查询，增减！！这也是该题所要求的一个一个知识点。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;

struct node{
	int a,b,lv,rv,cav;
	int flag;
}s[200000];

struct block{
	int x,y;
};

vector<block>vic;

int len(int num){
	return s[num].b-s[num].a+1;
}

void init(int num){
	s[num].lv=s[num].rv=s[num].cav=s[num].flag?0:len(num);
}

int Build(int x,int y,int num){
	s[num].a=x;	s[num].b=y;
	s[num].lv=s[num].rv=s[num].cav=len(num);
	s[num].flag=num==1?0:-1;
	if(x==y)
		return 0;
	int mid=(x+y)/2;
	Build(x,mid,num+num);
	Build(mid+1,y,num+num+1);
}

int search(int l,int num){
	if(s[num].a==s[num].b&&l==1)
		return s[num].a;
	if(s[num].flag!=-1){
		s[num+num].flag=s[num+num+1].flag=s[num].flag;
		init(num+num);	init(num+num+1);
		s[num].flag=-1;
	}
	if(s[num+num].cav>=l)
		return search(l,num+num);
	else if(s[num+num].rv+s[num+num+1].lv>=l)
		return s[num+num].b-s[num+num].rv+1;
	else if(s[num+num+1].cav>=l)
		return search(l,num+num+1);
	else return 0;
}

int modify(int x,int y,int flag,int num){
	if(x<=s[num].a&&y>=s[num].b){
		s[num].flag=flag;
		init(num);
		return 0;
	}
	if(s[num].flag!=-1){
		s[num+num+1].flag=s[num+num].flag=s[num].flag;
		s[num].flag=-1;
		init(num+num);	init(num+num+1);
	}
	int mid=(s[num].a+s[num].b)/2;
	if(x<=mid)
		modify(x,y,flag,num+num);	
	if(y>=mid+1)
		modify(x,y,flag,num+num+1);
	s[num].lv=s[num+num].lv;
	s[num].rv=s[num+num+1].rv;
	s[num].cav=max( max(s[num+num].cav,s[num+num+1].cav),s[num+num].rv+s[num+num+1].lv );
	if(s[num].lv==len(num+num))
		s[num].lv+=s[num+num+1].lv;
	if(s[num].rv==len(num+num+1))
		s[num].rv+=s[num+num].rv;
}

int count(int t){
	int beg=0,end=vic.size()-1;
	while(beg<=end){
		int mid=(beg+end)/2;
		if(vic[mid].x<=t)
			beg=mid+1;
		else
			end=mid-1;
	}
	return end;
}

int main(){
	int m,n,t,pos;
	char c[20];
	while(scanf("%d %d",&n,&m)!=EOF){
		Build(1,n,1);
		vic.clear();//一定要注意清空，不然您会wa的莫名其妙
		while(m--){
			scanf("%s",c);
			if(!strcmp(c,"Reset")){
				modify(1,n,0,1);
				vic.clear();
				printf("Reset Now\n");
			}
			else if(!strcmp(c,"New")){
				scanf("%d",&t);
				if(t>s[1].cav){
					printf("Reject New\n");
					continue;	
				}
				int id=search(t,1);
				if(id){
					modify(id,id+t-1,1,1);
					printf("New at %d\n",id);
				        pos=count(id)+1;
					block tempt;
					tempt.x=id;	tempt.y=id+t-1;
					vic.insert(vic.begin()+pos,tempt);
				}
				else
					printf("Reject New\n");
			}
			else if(!strcmp(c,"Free")){
				scanf("%d",&t);
				if(vic.size())
					 pos=count(t);
				else    pos=-1;
				if(pos==-1||vic[pos].y<t)
					printf("Reject Free\n");
				else{
					printf("Free from %d to %d\n",vic[pos].x,vic[pos].y);
					modify(vic[pos].x,vic[pos].y,0,1);
					vic.erase(vic.begin()+pos,vic.begin()+pos+1);
				}
				
			}
			else {
				int t;
                		scanf("%d",&t);
                		if(t<= vic.size()&&t> 0)
                    			printf("Get at %d\n" , vic[t-1].x);
               			 else
                    			printf("Reject Get\n");
			}			
		}
		printf("\n");
	}
	return 0;
}

题意：

题目有三种操作 :

D:  摧毁村庄

Q: 查询相连的村庄

R: 修复上次被摧毁的村庄

这个题目的关键部分就是 对线段的修改部分, 也是最难的部分, 这部分理解了, 这个题目就基本会了.

这个题目跟HOTEL类似，每个节点里包含：cav(这个节点所代表的区间，能够连续的最大子区间长度)，lv(左边开始数，连续区间长度)，rv(右边数起，连续区间的长度)，flag表示该区间是否存在连续区间。先把每个节点里的rv,lv,cav初始化成该区间的长度。

然后是查询函数，首先将节点的值往下传递（为了下面的操作），当要查询的节点位置小于该区间的mid，继续讨论，如果这个节点在从左子树的右边开始的连续区间内，则问题转换成：s[num+num].rv+search(mid+1,num+num+1);如果要查询的节点的位置大于mid，继续讨论，如果该节点在右子树左边开始的连续区间内，则问题转换成：s[num+num+1].lv+search(mid,num+num);最后当当前节点的c[num].cav==0(就是说这个区间不存在连续子区间，所以不必要继续找了，直接返回他的cav)或者c[num].cav==len(num)(就是说这个区间完全连续！当然返回啦)再或者这个区间只有一个节点了也直接返回，不用再找了。

然后就是更新函数了，更新函数首先还是把该节点的值往下传递，为了子树上面的操作，然后分左右子树进行分别更新，最关键的是

s[num].lv=s[num+num].lv;
	s[num].rv=s[num+num+1].rv;
	s[num].cav=max( max(s[num+num].cav,s[num+num+1].cav),s[num+num].rv+s[num+num+1].lv);
	if(s[num].lv==len(num+num))
		s[num].lv+=s[num+num+1].lv;
	if(s[num].rv==len(num+num+1))
		s[num].rv+=s[num+num].rv;

然后也没什么注意的地方了 呵呵 


#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;

struct node{
	int a,b;
	int lv,rv,cav,flag;
}s[200010];

int t[50010];

int len(int x){
	return s[x].b-s[x].a+1;
}

void init(int x){
	s[x].cav=s[x].lv=s[x].rv=s[x].flag?0:len(x);
}

int Build(int x,int y,int num){
	s[num].a=x;	s[num].b=y;
	s[num].flag=num==1?0:-1;
	s[num].lv=s[num].rv=s[num].cav=len(num);
	if(x==y){
		return 0;	
	}
	int mid=(x+y)/2;
	Build(x,mid,num+num);
	Build(mid+1,y,num+num+1);
}

int search(int x,int num){
	if(s[num].cav==0||s[num].cav==len(num)||s[num].a==s[num].b)
		return s[num].cav;
	if(s[num].flag!=-1){
		s[num+num].flag=s[num+num+1].flag=s[num].flag;
		s[num].flag=-1;
		init(num+num);	init(num+num+1);
	}
	int mid=(s[num].a+s[num].b)/2;
	if(x<=mid){
		if(x>mid-s[num+num].rv)
			return s[num+num].rv+search(mid+1,num+num+1);
		else 
			return search(x,num+num);
	}
	else{
		if(x<=mid+s[num+num+1].lv)
			return s[num+num+1].lv+search(mid,num+num);
		else
			return search(x,num+num+1);
	}
	
}

int modify(int x,int num,int flag){
	if(s[num].a==s[num].b){
		s[num].flag=flag;
		init(num);
		return 0;	
	}
	if(s[num].flag!=-1){
		s[num+num].flag=s[num+num+1].flag=s[num].flag;
		s[num].flag=-1;
		init(num+num);	init(num+num+1);
	}
	int mid=(s[num].a+s[num].b)/2;
	if(x<=mid)
		modify(x,num+num,flag);
	else 
		modify(x,num+num+1,flag);
	s[num].lv=s[num+num].lv;
	s[num].rv=s[num+num+1].rv;
	s[num].cav=max( max(s[num+num].cav,s[num+num+1].cav),s[num+num].rv+s[num+num+1].lv);
	if(s[num].lv==len(num+num))
		s[num].lv+=s[num+num+1].lv;
	if(s[num].rv==len(num+num+1))
		s[num].rv+=s[num+num].rv;
}

int main(){
    int n,x,cas,i,times;
    char c[20];
    while(scanf("%d %d",&n,&cas)!=EOF){
        memset(t,0,sizeof(t));
        times=1;
        Build(1,n,1);
        while(cas--){
            scanf("%s",c);
            if('D'==c[0]){
                scanf("%d",&x);
                t[times++]=x;
                modify(x,1,1);
            }    
            else if('Q'==c[0]){
                scanf("%d",&x);
                int k=search(x,1);
                printf("%d\n",k);
            }
            else{   if(times==1)
                    continue;
                x=t[--times];
                modify(x,1,0);
            }
        }
    }
    return 0;
}

题目大意：Bessie等牛到加拿大的桑德贝去增长文化修养外带观赏苏必利尔湖的阳光。按照导游的介绍，Bessie选择了著名的Cumberland大街上的Bullmoose宾馆作为居住的地点。

这座巨型宾馆在一条超长走廊上有N（1 ≤ N ≤ 50000）个排成一排的房间，每个房间都能欣赏到苏必利尔湖的好景色。现在所有的房间都是空的。

现在Bessie等旅客们正在不断地发出订房和退房要求。你需要接受M（1 ≤ M < 50000）条指令：

每条指令的第一个数字为1或2。如果是1，后面将有一个整数D表示顾客要预定的房间数。注意，这些房间必须是连续的。如果能够满足旅客的订房要求， 输出满足要求的第一个房间的编号（例如，要订房6间，输出3表示3, 4, 5, 6, 7, 8是满足要求的），这样的编号必须是可能的编号里面最靠前的。如果不能满足要求，输出0。

如果是2，后面将有两个整数X和D表示顾客要退掉X, X + 1, X + 2, ... , X + D - 1这D间房。对于这样的指令什么都不输出

题意分析：刚开始拿到这个题目也是不知道怎么建树，树节点里存放哪些信息，后来花了很久研究了解题报告，终于搞明白了。当你要查询连续的40个房间时候，左边有30个 右边有30个，你该怎么选择呢？这个时候如果用枚举各种情况 在逻辑上是可以的，但是肯定TLE。所以为了达到这种目的，我们要在节点里存放：lv(从左边数起，最大连续的房间数目)，rv(以右边第一点为起点，开始计数的最大连续房间数)，flag表示区间能否使用的（flag为0 表示可以使用），cav（指这个区间连续空余房间的最大值，相当于：lv,rv和交界处3个中的最大值），交界情况是指（左子树的）rv+（右子树的）lv，自己在纸上画一下，很明朗的；

建树的过程跟常规的 差不多，就是刚开始把rv,lv,cav初始化成当前节点区间的长度，因为题目给出初始情况，都是可以住人的，稍微注意一下，当num等于1时，flag赋值为1，因为这样在后面的操作，才能往下传递数值。

建立一个整理函数 ，当flag=0的时候整理当前节点的数值，把当前节点的rv,lv,cav，都更新成该区间长度。

查询操作：首先当前节点的数值往下传递，整理左右子树的rv,lv,cav；当查询到节点时，并且查询长度为1，则结束这次查询；先查询左子树是否有这么多空余房间，不行就查询左右交界处是否有这么多空余房间（即左子树的rv+右子树的lv），再查询右子树是否有这么多空余房间，如果都没，则返回0，结束查询。

更新操作注意的地方很多，首先更新的过程节点的值还得往下传递，这样保证了下一次在子节点的查询，当查询区间大于节点区间时，整理该区间，并且flag=-1标记该区间不能使用了；如果查询区间小于该 区间，则分别讨论左子树，右子树，注意一下两点，划分左右子树的界限是：x>=s[num].a和y>=mid+1;还有一个要注意的是，对左右子树更新完了 然后要回朔向上更新其父亲节点，因为父亲的lv就是左儿子的lv，画个图就能明白了，特别考虑一下：当s[num+num].lv==len(num+num)也就是说整个区间都是可以用的，那么父亲的s[num].lv=s[num].lv+s[num+num].lv;同理rv也是如此；

代码如下：

#include<iostream>
#include<stdio.h>
using namespace std;

struct node{
#include<iostream>
#include<stdio.h>
using namespace std;

struct node{
  int a,b;
  int rv,lv,cav,flag;
}s[200020];

int len(int x){
    return s[x].b-s[x].a+1;
}
int max(int x,int y){
	return x>y?x:y;
}

void init(int x){
   s[x].rv=s[x].lv=s[x].cav=s[x].flag?0:len(x);
}

int Build(int x,int y,int num){
   s[num].a=x;   s[num].b=y;
   s[num].lv=s[num].rv=s[num].cav=len(num);
   s[num].flag=num==1?0:-1;
   if(x==y)//
      return 0;
   int mid=(s[num].a+s[num].b)/2;//
   Build(x,mid,num+num);
   Build(mid+1,y,num+num+1);
   return 0;
}

int search(int num,int l){
   if(len(num)==1&&l==1)
      return s[num].a;
   if(s[num].flag!=-1){
      s[num+num].flag=s[num+num+1].flag=s[num].flag;
      s[num].flag=-1;
      init(num+num);
      init(num+num+1);
   }
   if(s[num+num].cav>=l)
      return search(num+num,l);
   else if(s[num+num].rv+s[num+num+1].lv>=l)
       return s[num+num].b-s[num+num].rv+1;
   else if(s[num+num+1].cav>=l)
      return search(num+num+1,l);
   else return 0;
}

int update(int x,int y,int flag,int num){
    if(x<=s[num].a&&y>=s[num].b){
         s[num].flag=flag;
         init(num);    
         return 0;
    }
    if(s[num].flag!=-1){
       s[num+num].flag=s[num+num+1].flag=s[num].flag;
       s[num].flag=-1;
       init(num+num);   init(num+num+1);
    }
    int mid=(s[num].a+s[num].b)/2;
    if(x<=mid)
         update(x,y,flag,num+num);//
    if(y>=mid+1)
         update(x,y,flag,num+num+1);//当初加了 else得出错误答案
    s[num].lv=s[num+num].lv;
    s[num].rv=s[num+num+1].rv;
    s[num].cav=max(max(s[num+num].cav,s[num+num+1].cav),s[num+num].rv+s[num+num+1].lv);
    if(s[num].lv==len(num+num))
        s[num].lv+=s[num+num+1].lv;
    if(s[num].rv==len(num+num+1))
        s[num].rv+=s[num+num].rv;

}

int main(){
	int n,cas,i,t,x,y;
	scanf("%d %d",&n,&cas);
	Build(1,n,1);
	for(i=1;i<=cas;i++){
		scanf("%d",&t);
		if(t==1){
			scanf("%d",&x);
			int k=search(1,x);
			printf("%d\n",k);
			if(k)
				update(k,k+x-1,1,1);
		}
		else if(t==2){
			scanf("%d %d",&x,&y);
			update(x,x+y-1,0,1);
		}
	}
	return 0;
}

  int a,b;
  int rv,lv,cav,flag;
}s[200020];

int len(int x){
    return s[x].b-s[x].a+1;
}

void init(int x){
   s[x].rv=s[x].lv=s[x].cav=s[x].flag?0:len(x);
}

int Build(int x,int y,int num){
   s[num].lv=s[num].rv=s[num].cav=len(num);
   s[num].a=x;   s[num].b=y;
   s[num].flag=num==1?0:-1;
   if(x=y)
      return 0;
   int mid=(s[num].a+s[num].b)/2
   Build(x,mid,num+num);
#include<iostream>
#include<stdio.h>
using namespace std;

struct node{
  int a,b;
  int rv,lv,cav,flag;
}s[200020];

int len(int x){
    return s[x].b-s[x].a+1;
}
int max(int x,int y){
	return x>y?x:y;
}

void init(int x){
   s[x].rv=s[x].lv=s[x].cav=s[x].flag?0:len(x);
}

int Build(int x,int y,int num){
   s[num].a=x;   s[num].b=y;
   s[num].lv=s[num].rv=s[num].cav=len(num);
   s[num].flag=num==1?0:-1;
   if(x==y)//
      return 0;
   int mid=(s[num].a+s[num].b)/2;//
   Build(x,mid,num+num);
   Build(mid+1,y,num+num+1);
   return 0;
}

int search(int num,int l){
   if(len(num)==1&&l==1)
      return s[num].a;
   if(s[num].flag!=-1){
      s[num+num].flag=s[num+num+1].flag=s[num].flag;
      s[num].flag=-1;
      init(num+num);
      init(num+num+1);
   }
   if(s[num+num].cav>=l)
      return search(num+num,l);
   else if(s[num+num].rv+s[num+num+1].lv>=l)
       return s[num+num].b-s[num+num].rv+1;
   else if(s[num+num+1].cav>=l)
      return search(num+num+1,l);
   else return 0;
}

int update(int x,int y,int flag,int num){
    if(x<=s[num].a&&y>=s[num].b){
         s[num].flag=flag;
         init(num);    
         return 0;
    }
    if(s[num].flag!=-1){
       s[num+num].flag=s[num+num+1].flag=s[num].flag;
       s[num].flag=-1;
       init(num+num);   init(num+num+1);
    }
    int mid=(s[num].a+s[num].b)/2;
    if(x<=mid)
         update(x,y,flag,num+num);//
    if(y>=mid+1)
         update(x,y,flag,num+num+1);//当初加了 else得出错误答案
    s[num].lv=s[num+num].lv;
    s[num].rv=s[num+num+1].rv;
    s[num].cav=max(max(s[num+num].cav,s[num+num+1].cav),s[num+num].rv+s[num+num+1].lv);
    if(s[num].lv==len(num+num))
        s[num].lv+=s[num+num+1].lv;
    if(s[num].rv==len(num+num+1))
        s[num].rv+=s[num+num].rv;

}

int main(){
	int n,cas,i,t,x,y;
	scanf("%d %d",&n,&cas);
	Build(1,n,1);
	for(i=1;i<=cas;i++){
		scanf("%d",&t);
		if(t==1){
			scanf("%d",&x);
			int k=search(1,x);
			printf("%d\n",k);
			if(k)
				update(k,k+x-1,1,1);
		}
		else if(t==2){
			scanf("%d %d",&x,&y);
			update(x,x+y-1,0,1);
		}
	}
	return 0;
}