1 #include <set>  2 #include <map>  3 #include <cmath>  4 #include <ctime>  5 #include <queue>  6 #include <stack>  7 #include <cctype>  8 #include <cstdio>  9 #include <string> 10 #include <vector> 11 #include <cstdlib> 12 #include <cstring> 13 #include <iostream> 14 #include <algorithm> 15 using namespace std; 16 typedef unsigned long long ull; 17 typedef long long ll; 18 const int inf = 0x3f3f3f3f; 19 const double eps = 1e-8; 20 template <class T> 21 inline bool scan_d(T &ret) 22 { 23     char c; 24     int sgn; 25     if(c=getchar(),c==EOF) return 0; 26     while(c!=‘-‘&&(c<‘0‘||c>‘9‘)) c=getchar(); 27     sgn=(c==‘-‘)?-1:1; 28     ret=(c==‘-‘)?0:(c-‘0‘); 29     while(c=getchar(),c>=‘0‘&&c<=‘9‘) ret=ret*10+(c-‘0‘); 30     ret*=sgn; 31     return 1; 32 } 33  34 const int maxn = 5e4+10; 35 int lv[maxn<<2],rv[maxn<<2], setv[maxn<<2];          //lv，rv数组可有可无，lsum rsum数组已经包含了他们的意义。 36 int lsum[maxn<<2],rsum[maxn<<2],sum[maxn<<2]; 37  38 void push_up(int l,int r,int pos) 39 { 40     lv[pos] = lv[pos<<1]; 41     rv[pos] = rv[pos<<1|1]; 42     lsum[pos] = lsum[pos<<1]; 43     rsum[pos] = rsum[pos<<1|1]; 44     sum[pos] = max(sum[pos<<1],sum[pos<<1|1]); 45     sum[pos] = max(sum[pos],rsum[pos<<1]+lsum[pos<<1|1]); 46     int mid = (l + r) >> 1; 47     if (rv[pos<<1] ==lv[pos<<1|1] && !rv[pos<<1]) 48     { 49         if (lsum[pos<<1] == mid - l + 1) 50             lsum[pos] += lsum[pos<<1|1]; 51         if (rsum[pos<<1|1] == r - mid) 52             rsum[pos] += rsum[pos<<1]; 53         sum[pos] = max(sum[pos],rsum[pos<<1]+lsum[pos<<1|1]); 54     } 55 } 56  57 void push_down(int l,int r,int pos) 58 { 59     if (~setv[pos]) 60     { 61         int mid = (l + r) >> 1; 62         setv[pos<<1] = setv[pos<<1|1] = setv[pos]; 63         lv[pos<<1] = setv[pos]; 64         lv[pos<<1|1] = setv[pos]; 65         rv[pos<<1] = setv[pos]; 66         rv[pos<<1|1] = setv[pos]; 67         lsum[pos<<1] = (setv[pos] ? 0 : (mid-l+1)); 68         rsum[pos<<1] = (setv[pos] ? 0 : (mid-l+1)); 69         lsum[pos<<1|1] = (setv[pos] ? 0 : (r-mid)); 70         rsum[pos<<1|1] = (setv[pos] ? 0 : (r-mid)); 71         sum[pos<<1] = (setv[pos] ? 0 : (mid-l+1)); 72         sum[pos<<1|1] = (setv[pos] ? 0 : (r-mid)); 73         setv[pos] = -1; 74     } 75 } 76  77 void build (int l,int r,int pos) 78 { 79     if (l == r) 80     { 81         rv[pos] = lv[pos] = 0; 82         sum[pos] = lsum[pos] = rsum[pos] = 1; 83         return; 84     } 85     int mid = (l + r) >> 1; 86     build(l,mid,pos<<1); 87     build(mid+1,r,pos<<1|1); 88     push_up(l,r,pos); 89 } 90  91 void update(int l,int r,int pos,int ua,int ub,int val) 92 { 93     if (ua <= l && ub >= r) 94     { 95         setv[pos] = val; 96         lv[pos] = val; 97         rv[pos] = val; 98         lsum[pos] = (val ? 0 : (r-l+1)); 99         rsum[pos] = (val ? 0 : (r-l+1));100         sum[pos] =  (val ? 0 : (r-l+1));101         return;102     }103     int mid = (l + r) >> 1;104     push_down(l,r,pos);105     if (ua <= mid)106         update(l,mid,pos<<1,ua,ub,val);107     if (ub > mid)108         update(mid+1,r,pos<<1|1,ua,ub,val);109     push_up(l,r,pos);110 }111 112 int query(int l,int r,int pos,int x)113 {114     if (lsum[pos] >= x)115     {116         return l;117 118     }119     int mid = (l + r) >> 1;120     push_down(l,r,pos);121     if (sum[pos<<1] >= x)122          return query(l,mid,pos<<1,x);123     /*else if (rsum[pos<<1]&&rsum[pos<<1] + lsum[pos<<1|1] >= x)          //注释部分是错误的，，看起来很像但是不一样的124         return query(l,mid,pos<<1,rsum[pos<<1]);*/125     else if (rsum[pos<<1] + lsum[pos<<1|1] >= x)126         return mid+1-rsum[pos<<1];127     else128         return query(mid+1,r,pos<<1|1,x);129 }130 131 int main(void)132 {133     #ifndef ONLINE_JUDGE134     freopen("in.txt","r",stdin);135     #endif136     int n,q;137     while (~scanf ("%d%d",&n,&q))138     {139         build(1,n,1);140         memset(setv,-1,sizeof(setv));141         for (int i = 0; i < q; i++)142         {143             int op,x,y;144             scanf ("%d",&op);145             if (op == 1)146             {147                 scanf ("%d",&x);148                 if (sum[1] < x)149                 {150                     printf("0\n");151                     continue;152                 }153                 int p = query(1,n,1,x);154                 printf("%d\n",p);155                 update(1,n,1,p,p+x-1,1);156             }157             else158             {159                 scanf ("%d%d",&x,&y);160                 update(1,n,1,x,y+x-1,0);161             }162         }163     }164     return 0;165 }