> Source Code
> Problem: 3667		User: caizixian
> Memory: 3296K		Time: 594MS
> Language: C++		Result: Accepted
> 
>     * Source Code
> 
>       #include <stdio.h>
> 
>        
> 
>       #define Max(a, b) ((a)>(b)?(a):(b))
> 
>        
> 
>       const int N = 50010;
> 
>        
> 
>       struct ST {int i,j,m,l,r,c,lc,rc;} st[2*N]; //区????´å®½åº¦çš„2å€�
> 
>       int up, n;
> 
>        
> 
>       void bd(int d, int x, int y) {
> 
>             st[d].i = x, st[d].j = y, st[d].m = (x+y)/2;
> 
>             st[d].c = st[d].lc = st[d].rc = y-x;
> 
>             if(x < y-1) {
> 
>                  st[d].l = ++up; bd(up, x, st[d].m);
> 
>                  st[d].r = ++up; bd(up, st[d].m, y);
> 
>             }
> 
>       }
> 
>        
> 
>       void spread(int d) {
> 
>             if(st[d].c == st[d].j-st[d].i) {
> 
>                  int& l = st[d].l, &r = st[d].r;
> 
>                  st[l].c = st[l].lc = st[l].rc = st[l].j-st[l].i;
> 
>                  st[r].c = st[r].lc = st[r].rc = st[r].j-st[r].i;
> 
>             } else if(st[d].c == 0) {
> 
>                  int& l = st[d].l, &r = st[d].r;
> 
>                  st[l].c = st[l].lc = st[l].rc = 0;
> 
>                  st[r].c = st[r].lc = st[r].rc = 0;
> 
>             }
> 
>       }
> 
>        
> 
>       void update(int d) {
> 
>             st[d].c = Max(Max(st[st[d].l].c, st[st[d].r].c), st[st[d].l].rc + st[st[d].r].lc);
> 
>             if(st[st[d].l].c == st[st[d].l].j-st[st[d].l].i) {
> 
>                  st[d].lc = st[st[d].l].c + st[st[d].r].lc;
> 
>             } else st[d].lc = st[st[d].l].lc;
> 
>             if(st[st[d].r].rc == st[st[d].r].j-st[st[d].r].i) {
> 
>                  st[d].rc = st[st[d].r].rc + st[st[d].l].rc;
> 
>             } else st[d].rc = st[st[d].r].rc;
> 
>       }
> 
>        
> 
>       void Empty(int d, int x, int y) {
> 
>             if(x <= st[d].i && y >= st[d].j) {
> 
>                  st[d].c = st[d].lc = st[d].rc = 0;
> 
>                  return;
> 
>             }
> 
>        
> 
>             spread(d);
> 
>        
> 
>             if(x < st[d].m) Empty(st[d].l, x, y);
> 
>             if(y > st[d].m) Empty(st[d].r, x, y);
> 
>        
> 
>             update(d);
> 
>       }
> 
>        
> 
>       void Fill(int d, int x, int y) {
> 
>             if(x <= st[d].i && y >= st[d].j) {
> 
>                  st[d].c = st[d].lc = st[d].rc = st[d].j-st[d].i;
> 
>                  return;
> 
>             }
> 
>        
> 
>             spread(d);
> 
>        
> 
>             if(x < st[d].m) Fill(st[d].l, x, y);
> 
>             if(y > st[d].m) Fill(st[d].r, x, y);
> 
>        
> 
>             update(d);
> 
>       }
> 
>        
> 
>       int Get(int d, int l) {
> 
>            
> 
>             spread(d);
> 
>        
> 
>             if(st[d].c < l) return -1;
> 
>             if(st[st[d].l].c >= l)
> 
>                  return Get(st[d].l, l);
> 
>             else if(st[st[d].l].rc + st[st[d].r].lc >= l) {
> 
>                  return st[st[d].l].j-st[st[d].l].rc;
> 
>             }
> 
>             return Get(st[d].r, l);
> 
>       }
> 
>        
> 
>       int main()
> 
>       {
> 
>             int i, nq, cmd, x, l, y;
> 
>             up = 0;
> 
>             scanf("%d%d", &n, &nq);
> 
>             bd(0, 0, n);
> 
>             while(nq--) {
> 
>                  scanf("%d", &cmd);
> 
>                  if(cmd == 1) {
> 
>                        scanf("%d", &l);
> 
>                        x = Get(0, l);
> 
>                        if(x != -1)
> 
>                             Empty(0, x, x+l);
> 
>                        printf("%d\n", x+1);
> 
>                  } else {
> 
>                        scanf("%d%d", &x, &l);
> 
>                        Fill(0, x-1, x+l-1);
> 
>                  }
> 
>             }
> 
>             return 0;
> 
>       }
>