1 //Accepted    3728 KB    1079 ms  2 //线段树 区间合并  3 #include <cstdio>  4 #include <cstring>  5 #include <iostream>  6 #include <queue>  7 #include <cmath>  8 #include <algorithm>  9 using namespace std; 10 /** 11   * This is a documentation comment block 12   * 如果有一天你坚持不下去了，就想想你为什么走到这儿！ 13   * @authr songt 14   */ 15 const int imax_n = 500005; 16 struct node 17 { 18     int l,r; 19     int L1,R1; 20     int sum1; 21     int change;   //change -1 区间没有改变  0区间变成0 1区间变成1 22 }f[imax_n*4]; 23 int max(int a,int b) 24 { 25     return a>b?a:b; 26 } 27 int min(int a,int b) 28 { 29     return a<b?a:b; 30 } 31 void swap(int &a,int &b) 32 { 33     int t=a; 34     a=b; 35     b=t; 36 } 37 void pushUp(int t) 38 { 39     int lLen=f[2*t].r-f[2*t].l+1; 40     int rLen=f[2*t+1].r-f[2*t+1].l+1; 41     f[t].L1=f[2*t].L1; 42     if (f[2*t].L1==lLen) f[t].L1+=f[2*t+1].L1; 43     f[t].R1=f[2*t+1].R1; 44     if (f[2*t+1].R1==rLen) f[t].R1+=f[2*t].R1; 45     f[t].sum1=max(f[2*t].sum1,f[2*t+1].sum1); 46     f[t].sum1=max(f[t].sum1,f[2*t].R1+f[2*t+1].L1); 47 } 48 void pushDown(int t) 49 { 50     if (f[t].change!=-1) 51     { 52         f[2*t].change=f[t].change; 53         f[2*t+1].change=f[t].change; 54         f[t].change=-1; 55         f[2*t].L1=f[2*t].R1=f[2*t].sum1=(f[2*t].r-f[2*t].l+1)*f[2*t].change; 56         f[2*t+1].L1=f[2*t+1].R1=f[2*t+1].sum1=(f[2*t+1].r-f[2*t+1].l+1)*f[2*t+1].change; 57     } 58 } 59 void build(int t,int l,int r) 60 { 61     f[t].l=l; 62     f[t].r=r; 63     f[t].change=-1; 64     if (l==r) 65     { 66         f[t].L1=f[t].R1=f[t].sum1=1; 67         return ; 68     } 69     int mid=(f[t].l+f[t].r)/2; 70     build(2*t,l,mid); 71     build(2*t+1,mid+1,r); 72     pushUp(t); 73 } 74 void update(int t,int l,int r,int c) 75 { 76     if (f[t].l==l && f[t].r==r) 77     { 78         f[t].change=c; 79         f[t].L1=f[t].R1=f[t].sum1=f[t].change*(f[t].r-f[t].l+1); 80         return ; 81     } 82     pushDown(t); 83     int mid=(f[t].l+f[t].r)/2; 84     if (r<=mid) update(2*t,l,r,c); 85     else 86     { 87         if (l>mid) update(2*t+1,l,r,c); 88         else 89         { 90             update(2*t,l,mid,c); 91             update(2*t+1,mid+1,r,c); 92         } 93     } 94     pushUp(t); 95 } 96 int query(int t,int k) 97 { 98     //printf("f[%d].sum1=%d\n",t,f[t].sum1); 99     if (f[t].l==f[t].r)100     {101         if (f[t].sum1<k) return -1;102         else return f[t].l;103     }104     pushDown(t);105     if (f[t].sum1<k) return -1;106     if (f[2*t].sum1>=k) return query(2*t,k);107     if (f[2*t].R1+f[2*t+1].L1>=k) return f[2*t].r-f[2*t].R1+1;108     if (f[2*t+1].sum1>=k) return query(2*t+1,k);109     return -1;110 }111 int n,m;112 int op,x,y;113 void slove()114 {115     build(1,1,n);116     for (int i=1;i<=m;i++)117     {118         scanf("%d",&op);119         if (op==1)120         {121             scanf("%d",&x);122             int t=query(1,x);123             //printf("query=%d\n",t);124             if (t==-1)125             printf("0\n");126             else127             {128                 printf("%d\n",t);129                 update(1,t,t+x-1,0);130             }131         }132         else133         {134             scanf("%d%d",&x,&y);135             update(1,x,x+y-1,1);136         }137     }138 }139 int main()140 {141     while (scanf("%d%d",&n,&m)!=EOF)142     {143         slove();144     }145     return 0;146 }