题目链接：
题目大意：
插队的问题，每个案例给出n，代表有n个插队的，每个给出p,v，意思是代号为v的人插在了第p个人的后面，问最后的队伍的排列？
解题思路：
如果从前往后递推，每次插入在前面的话，后面的人都需要往后移动，所以考虑从后往前放
从后往前退的话每次可以推到确定的位置，插入在位置为i的地方，说明按从前往后放的时候前面有i个人，从后往前放的话就是前面有i个空格，放在第i+1个空格的地方，这样逆序放的话每次都可以放在确定的位置，不用移动。
线段树存的是区间内空格的数目，每次放的时候，位置需要加1，因为位置i说明放在前面有i个空格，该点在第i+1个空格处。
1 #include2 #include 3 #define MID(l, r) (l + (r - l) / 2) 4 #define lson(o) (o * 2) 5 #define rson(o) (o * 2 + 1) 6 using namespace std; 7 typedef long long ll; 8 const int INF = 1e9 +7; 9 const int maxn = 1e6 + 10;10 int h, w, n;11 struct node12 {13 int l, r, sum;14 }tree[maxn];15 int ans[maxn];16 void build(int o, int l, int r)17 {18 tree[o].l = l, tree[o].r = r;19 if(l == r)20 {21 tree[o].sum = 1;22 return;23 }24 int m = MID(l, r);25 int lc = lson(o), rc = rson(o);26 build(lc, l, m);27 build(rc, m + 1, r);28 tree[o].sum = tree[lc].sum + tree[rc].sum;29 }30 void insert(int o, int a, int b)//a个空位31 {32 if(tree[o].l == tree[o].r)33 {34 ans[tree[o].l] = b;35 tree[o].sum = 0;36 return;37 }38 int lc = lson(o), rc = rson(o);39 if(a <= tree[lc].sum)insert(lc, a, b);//空位数目小于等于左子树，在左子树中插入40 else insert(rc, a - tree[lc].sum, b);//空位数目大于左子树，在右子树插入，此时a需要减去左子树的空位数目41 tree[o].sum = tree[lc].sum + tree[rc].sum;//在插如之后空位数目发生变化，需要维护本节点的sum值42 }43 int a[maxn], b[maxn];44 int main()45 {46 int n, m;47 while(scanf("%d", &n) != EOF)48 {49 build(1, 1, n);50 for(int i = 0; i < n; i++)scanf("%d%d", &a[i], &b[i]), a[i]++;//空位数目自加一，表示自己在第a[i]个空位处51 for(int i = n - 1; i >= 0; i--)52 {53 insert(1, a[i], b[i]);54 }55 for(int i = 1; i < n; i++)printf("%d ", ans[i]);56 printf("%d\n", ans[n]);57 58 }59 return 0;60 }