HDU 2871(Memory Control)

题目分析:题目有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;
}

 

HDU 1540 Tunnel Warfare

题意:

题目有三种操作 :

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;
}

 

PKU 2192 Zipper 的解题报告

题目分析:题目大致意思是让你判断字符串三是否可以由字符串1,2组合而成,前提是字符串1,2的字母前后顺序不改变。
              又是一个动态规划题目,用dp[i][j]表示字符串a的前i个和字符串b的前j个和字符串c的前i+j-1段匹配的逻辑值。分析可知:要求得dp[i][j],可以划分为两个子问题:1

dp[i-1][j]&&a[i-1]==c[j+i-1] or 2:dp[i][j-1]&&b[j-1]==c[i+j-1]。 如果这两个任何一个可以满足,则dp[i][j]=true;否则dp[i][j]=false.

             状态转移方程:dp[i][j]=( (dp[i-1][j]and a[i-1]==c[i+j-1]) or (dp[i][j-1] and b[j-1]==c[i+j-1]) );

  源程序:

#include<iostream>

       #include<cstring>

       using namespace std;

       int main(){

                char a[201],b[201],c[401];

                 int dp[201][201];

                 int n;

                 cin>>n;

                  for(int k=1;k<=n;k++){

                         scanf("%s%s%s",a,b,c);

                         int len1=strlen(a),len2=strlen(b);

                         for(int i=0;i<=len1;i++)

                                   for(int j=0;j<=len2;j++)

                                                if(i==0||j==0)

                                                       dp[i][j]=1;

                                                  else

                                                         if( (dp[i-1][j]&&a[i-1]==c[i+j-1]) || (dp[i][j-1] && b[j-1]==c[i+j-1]))  

                                                                     dp[i][j]=1;

                                                          else

                                                                      dp[i][j]=0;     

                         if(dp[len1][len2]==1)

                                   printf("Data set %d: yes\n",k);
                         else
                                   printf("Data set %d: no\n",k);          

                  }                 

         }

总结:在写代码的时候注意i,j是从0开始遍历到len1,len2,因为计算第一个是以前一个为真为前提的,所以i==0或者j==0时,应该赋真值。

PKU_2081 Recaman's Sequence

题目分析:也属于动态规划的 一个题目,当求得的a[m]为正值并且在前面的序列中未曾出现过 a[m]=a[m-1]-m。反之a[m]=a[m-1]+m;由于处理的数据非常多 非常容易超时,所以必须一次性计算出0<=i<500000内所有a[i]的值,然后输入i的时候直接输出就可以了。

提示:因为数据非常多所以要用个数组记录a[i]是否出现过,切忌用来记录的数组一定要开的大一点 不然你会发现一直编译过不了,出现很奇怪的错误。

源程序:

#include<iostream>

using namespace std;

bool sim[3500000]={false};

int a[500001]={0};

int main(){

    int i,s,n;

    for(i=1;i<500000;i++){

         s=a[i-1]-i;

         if(s>0&&!sim[s])

              a[i]=s;

          else

              a[i]=a[i-1]+i;

          sim[a[i]]=true; 

    }

    while(cin>>n&&n!=-1)

          cout<<a[n]<<endl;

     return 0;

}

总结:只要细心点,注意数组开的合适点,还有先把所有的0<=i<500000的都计算好,然后直接读取输出就可以AC了^_^.

PKU 1088滑雪解题报告

题 目分析:这个题目需要求出每个阶段的最大滑雪长度,状态转移的选择条件有两个:一:这个阶段的四个方向的数有比他本身小的,另一个条件:选择出满足条件一 的几个数中滑雪长度最大的那个。这样就完成了一次状态转移。这样不断递推下去就可以求出每个阶段的滑雪最大长度,然后遍历每个节点,找出最大的那个长度就 可以了。

提示:要用到记忆搜索,这样能避免重复递归。

源程序:

#include<iostream>

     using namespace std;

     int h[101][101];

     int sim[101][101];

     int r,c;

     int dp(int i,int j){

         int dir[2][4]={-1,0,1,0,0,1,0,-1};

         int m,max=0;//如果上下左右没有一个比自己小,这时候h[i][j]=max+1=1;这就是为什么要把max初始为0。

         if(h[i][j]!=0)

               return h[i][j];

         else{

               for(int k=0;k<4;k++){

                    if(i+dir[0][k]>=0&&i+dir[0][k]<r&&j+dir[1][k]>=0&&j+dir[1][k]<c)

                           if(sim[i][j]>sim[i+dir[0][k]][j+dir[1][k]]){

                                  m=dp(i+dir[0][k],j+dir[1][k]);

                                  if(max<m)//这个是用来在相邻的四个元素中(有时候没有四个)选择滑雪长度最大的      路径作为h[i][j]的路径。

                                      max=m;     

                           }

                           else

                               continue;  

               }

              return max+1;//因为在这里max是上下左右几个元素的最大滑雪长度,而h[i][j]的值为包括了自己,所以要加上1。^_^注意这些相信你会AC了。

         }

     }

int soulve(){

    int max=0;

    for(int i=0;i<r;i++)

        for(int j=0;j<c;j++){

              h[i][j]=dp(i,j);

              if(max<h[i][j])

                    max=h[i][j];

        }    

    return max;         

}

int main(){

    while(cin>>r>>c){

         for(int i=0;i<r;i++)

             for(int j=0;j<c;j++){

                  cin>>sim[i][j];

                  h[i][j]=0;

             }

         cout<<soulve()<<endl;        

    }

}

总结:在这里值得注意的就是,记忆化搜索。在计算每个节点的滑雪最大值时要注意,用于比较上下左右的最大滑雪长度的语句应该紧跟递归其后。

poj 3259 :Wormholes (bellman_ford)

题意:John的农场里field块地,path条路连接两块地,hole个虫洞,虫洞是一条单向路,不但会把你传送到目的地,而且时间会倒退Ts。我们的任务是知道会不会在从某块地出发后又回来,看到了离开之前的自己。

题目分析:这题存在负权所以Dijkstra在这里就不能用了,这个题目的本质就是判断负权是否存在,如果存在就可以满足题目要求。没有的话就不可能。

#include<iostream>

using namespace std;

const int inf=10000;

int num_count,edg;

struct {

      int star;

      int end;

      int time;

}sim[10000];

int dic[10000];

bool judge(){

      int flag;

      for(int i=2;i<=num_count;i++)

              dic[i]=inf;

     for(int i=1;i<=num_count;i++){

            flag=1;//加个判断是否完全松弛,优化算法,减少运行时间。

            for(int j=1;j<=edg;j++){  

                     int u=sim[j].star;

                     int v=sim[j].end;

                     int w=sim[j].time;

                     if(dic[v]>dic[u]+w){//松弛操作

                               flag=0;

                               dic[v]=dic[u]+w ;

                      }                          

            }

            if(flag)

                    break;

     }

            for(int j=1;j<=num_count;j++){//判断是否存在负权。

                     int u=sim[j].star;

                     int v=sim[j].end;

                     int w=sim[j].time;

                     if(dic[v]>dic[u]+w)

                               return false;

             }

             return true;

}

int main(){

      int cas,n,path,hole;

      cin>>cas;

      while(cas--){

             int a,b,c,k=0;

             scanf("%d%d%d",&n,&path,&hole);

             for(int i=1;i<=path;i++){

                      scanf("%d%d%d",&a,&b,&c);

                      k++;

                      sim[k].star=a;

                      sim[k].end=b;

                      sim[k].time=c;

                       k++;   

                      sim[k].star=b;

                      sim[k].end=a;

                      sim[k].time=c;

             }

            for(int i=1;i<=hole;i++){

                       scanf("%d%d%d",&a,&b,&c);

                       k++;

                       sim[k].star=a;

                       sim[k].end=b;

                       sim[k].time=-c;

           }

     num_count=n;

     edg=k;

     if(!judge())

             cout<<"YES"<<endl;

     else

             cout<<"NO"<<endl;

     }

    return 0;

}

题目总结:开始的时候用n,edg作为节点个数和边的个数,在主函数,和功能函数中都是用这个,发现即使把他们定义为全局变量都会出错,后来决定分别用四个变量来完成记录点数,边数。

这个题目的思路就是判断是否存在负权,只要进行松弛n次,然后判断是否达到完全松弛,如果没,就说明存在负权。

 

HDU1205吃糖果

题目思路:

我们发现,如果最大堆-次大堆<=1,那么问题肯定有解:我们可以从最大和次大里面每次拿一个,然后等他们和第三大堆相等的时候,每次从三堆里面各拿一个,等他们和第四大堆相等的时候,每次从四堆里面各拿一个,这样一直拿完所有堆。

问题变成了能不能使得最大堆-次大堆<=1,所以之前我们会从次大堆之外的那些堆里面取,来让最大堆减少,如果能减到:最大堆-次大堆<=1,那么原问题有解。

能否减到要看:

sum - max - max2 >= max - max2 - 1

是否成立,其中sum为总和,max为最大堆,max2为次大。

整理得:

2 * max - sum <= 1

应该这样就可以了。

源程序代码:

#include<stdio.h>
int main()
{
    long n,m,x,max;
    long sum;
    scanf("%d",&n);
    while(n--)
   {
        scanf("%d",&m);
        sum=0;
        max=0;
        while(m--)
         {
           scanf("%d",&x);
           sum+=x;
           if(max<x)
      max=x;
         }
   max<=sum-max+1?    
    printf("Yes\n"): printf("No\n");
    }
return 0;
}

 

POJ 3667 hotel(线段树经典题目)

题目大意: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;
}