1 #include <cstdio> 2 #include <iostream> 3 using namespace std; 4 const int MAXN=50001<<2; 5 #define chl l,mid,rt*2 6 #define chr mid+1,r,rt*2+1 7 int msum[MAXN],lsum[MAXN],rsum[MAXN],la[MAXN]; 8 void pushup(int l,int r,int rt){ 9     int mid=(l+r)/2;10     lsum[rt]=lsum[rt*2]==mid-l+1?mid-l+1+lsum[rt*2+1]:lsum[rt*2];11     rsum[rt]=rsum[rt*2+1]==r-mid?r-mid+rsum[rt*2]:rsum[rt*2+1];12     msum[rt]=max(max(msum[rt*2],msum[rt*2+1]),lsum[rt*2+1]+rsum[rt*2]);13 }14 void pushdown(int l,int r,int rt){15     if(la[rt]!=-1){16         int mid=(l+r)/2;17         la[rt*2]=la[rt*2+1]=la[rt];18         msum[rt*2]=lsum[rt*2]=rsum[rt*2]=la[rt]*(mid-l+1);19         msum[rt*2+1]=lsum[rt*2+1]=rsum[rt*2+1]=la[rt]*(r-mid);20         la[rt]=-1;21     }22 }23 void build(int l,int r,int rt){24     msum[rt]=lsum[rt]=rsum[rt]=r-l+1;25     la[rt]=-1;26     if(l==r)return ;27     int mid=(l+r)/2;28     build(chl);29     build(chr);30 }31 void update(int x,int y,int c,int l,int r,int rt){32     if(x<=l&&y>=r){33         msum[rt]=lsum[rt]=rsum[rt]=c*(r-l+1);34         la[rt]=c;35         return;36     }37     pushdown(l,r,rt);38     int mid=(l+r)/2;39     if(x<=mid)update(x,y,c,chl);40     if(y>mid)update(x,y,c,chr);41     pushup(l,r,rt);42 }43 int query(int c,int l,int r,int rt){44     if(l==r)return l;45     pushdown(l,r,rt);46     int mid((l+r)/2);47     if(msum[rt*2]>=c)return query(c,chl);48     else if(rsum[rt*2]+lsum[rt*2+1]>=c)return mid-rsum[rt*2]+1;49     else query(c,chr);50 }51 int main(){52     //freopen("test.txt","r",stdin);53     int n,m,sw,a,b;54     scanf("%d%d",&n,&m);55     build(1,n,1);56     while(m--){57         scanf("%d",&sw);58         if(sw==1){59             scanf("%d",&a);60             if(msum[1]<a){printf("0\n");continue;}61             int q=query(a,1,n,1);62             printf("%d\n",q);63             update(q,q+a-1,0,1,n,1);64         }65         else {66             scanf("%d%d",&a,&b);67             update(a,a+b-1,1,1,n,1);68         }69     }70     return 0;71 }