1 /* 2     结点存储下面有几个空位 3     每次从根结点往下找找到该插入的位置， 4     同时更新每个节点的值 5 */ 6 #include 
     
       7 #define lson l, m, rt << 1 8 #define rson m+1, r, rt << 1 | 1 9 10 const int MAX_N = 200000 + 10;11 int pos[MAX_N], val[MAX_N];12 int sum[MAX_N << 2];13 int que[MAX_N];14 int id;15 16 void build(int l, int r, int rt)17 {18     sum[rt] = r - l + 1;        //节点有多少个空位置19     if (l == r)        return ;20     int m = (l + r) >> 1;21     build (lson);22     build (rson);23 }24 25 void update(int p, int l, int r, int rt)26 {27     sum[rt]--;                    //插入一个减少一个空位置28     if (l == r)                    //找到了传递该位置29     {30         id = l;31         return ;32     }33     int m = (l + r) >> 1;34     if (p <= sum[rt<<1])35     {36         update (p, lson);37     }38     else39     {40         p -= sum[rt<<1];    //减去41         update (p, rson);42     }43 }44 45 int main(void)        //POJ 2828 Buy tickets46 {47     //freopen ("inE.txt", "r", stdin);48     int n;49 50     while (~scanf ("%d", &n))51     {52         build (1, n, 1);53         for (int i=1; i<=n; ++i)54         {55             scanf ("%d%d", &pos[i], &val[i]);56         }57         for (int i=n; i>=1; --i)        //最后插入的位置不变58         {59             update (pos[i]+1, 1, n, 1);60             que[id] = val[i];61         }62         printf ("%d", que[1]);63         for (int i=2; i<=n; ++i)64         {65             printf (" %d", que[i]);66         }67         puts ("");68     }69 70     return 0;71 }