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;

      }

• 思路跟你一样，对拍了一下发现query少了个spread ！感谢啊分享 (4057) iyixiang 2010-08-16 20:04:45