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