Contents

1. 1. hdu 2828
2. 2. ★关键是这里如何处理★

hdu 2828

参考：http://www.cnblogs.com/CheeseZH/archive/2012/04/29/2476134.html

首先是插入3 69
1，4结点有4个位置，
1，2结点有2个位置，小于3，因此放到1，4结点右孩子，且1，4结点空位置减1
到了1，4右孩子后，只要找到第3-2=1个位置即可，而3，4结点的左孩子3，3含有1个空位置，1>=1，所以放到3，3位置了。

插入2 33

★关键是这里如何处理★

　　插入2 51
此时1，4的左孩子只有1个位置，1<2，所以只能放到1，4的右孩子3，4上
3，4的左孩子有0个位置，所以只能放在3，4的右孩子4，4上。

　　这题刚看到的时候本来是想用数组版双向链表做的，但双向链表确实练的不熟，想了一个小时，没实现出来，还是用线段树解吧，下次有时间再回来想
虽然想到了要倒着插入，但还是没想到node里要存空位置数，看了网上的题解才知道，不过确实是好题

/*  若左子树的空格数大于等于要放入的位置，则搜索左子树,(说明可以插入)  否则，搜索右子树，(说明前面已经被插入了只能往后面退了)由于左边有一些空位置，只需要搜索右子树的部分空位置，使左右空位置之和为要搜索的位置。*/
  若左子树的空格数大于等于要放入的位置，则搜索左子树,(说明可以插入)
  否则，搜索右子树，(说明前面已经被插入了只能往后面退了)由于左边有一些空位置，只需要搜索右子树的部分空位置，使左右空位置之和为要搜索的位置。
*/

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define Lson(x) (x<<1)
#define Rson(x) (x<<1|1)
#define Mid(x, y) ((x + y) >> 1)

#define MAXN 200005

int que[MAXN];

struct Node{
    int sum;                //存该区间内的空位置数
};

Node node[MAXN << 2];

void push_up(int pos){

    node[pos].sum = node[Lson(pos)].sum + node[Rson(pos)].sum;
}

void build(int left, int right, int pos){

    if (left == right) {
        node[pos].sum = 1;
        return;             //初始时，叶子节点的空位置数为1
    }
    int mid = Mid(left, right);
    build(left, mid, Lson(pos));
    build(mid + 1, right, Rson(pos));
    push_up(pos);
}

void update(int index, int val, int left, int right, int pos){

    if (left == right) {
        que[left] = val;    //left == right,叶子节点里插入记录到que数组中
        node[pos].sum = 0;
        return;             //插入元素后将该叶子节点的空位置数为0
    }
    int mid = Mid(left, right);
    if (node[Lson(pos)].sum >= index)   //重点就在下面这部分
        update(index, val, left, mid, Lson(pos));
    else
        update(index - node[Lson(pos)].sum, val, mid + 1, right, Rson(pos));
    push_up(pos);           //向上更新
}

int main(){

    int n, index[MAXN], val[MAXN], i;

    while (scanf("%d", &n) != EOF)
    {
        build (1, n, 1);
        for (i = 1; i <= n; i++)
             scanf ("%d %d", &index[i], &val[i]);
        for (i = n; i > 0; i--)                    //倒过来插入
             update(index[i] + 1, val[i], 1, n, 1);//从下标1开始
        for (i = 1; i <= n; i++)
             printf ("%d ", que[i]);
        printf ("\n");
    }
    return 0;
}