https://vjudge.net/problem/POJ-2828
题目意思：有n个数，进行n次操作，每次操作有两个数pos, ans。pos的意思是把ans放到第pos 位置的后面，pos后面的数就往后推一位。最后输出每个位置的ans。
思路：根据题 目可知，最后插入的位置的数才是最终不变的数，所以可以从最后的输入作第1个放入，依此类推，倒插入。在插入时也有一定的技术，首先创建一棵空线段树时，每个节点记录当前范围内有多少个空位置。在插入时，要注意，一个数放入之后那么这个位置就不用管了，那么树中所有的空位置就是余下的数所对应的位置，也就是把余下的数又可以看作是一个新的集合。那么每次插入都是当前集合的第1次放。
1 #include <iostream>
2 #include <algorithm>
3 #include <string>
4 #include <sstream>
5 #include <set>
6 #include <vector>
7 #include <stack>
8 #include <map>
9 #include <queue>
10 #include <deque>
11 #include <cstdlib>
12 #include <cstdio>
13 #include <cstring>
14 #include <cmath>
15 #include <ctime>
16 #include <functional>
17 // #include <bits/stdc++.h>
18 using namespace std;
19
20 int n,ans[1000000];
21
22 struct node
23 {
24 int n,val;
25 }a[1000000];
26
27 struct tree
28 {
29 int l,r,n;
30 }b[1000000];
31
32 void init()
33 {
34 int i,j,k;
35 for(k=1;k<n;k<<=1);
36 for(i=k;i<2*k;i++)
37 {
38 b[i].l=b[i].r=i-k+1;
39 b[i].n=1;//每个叶子节点只能放入一个人
40 }
41 for(i=k-1;i>0;i--)
42 {
43 b[i].l=b[2*i].l;
44 b[i].r=b[2*i+1].r;
45 b[i].n=b[2*i].n+b[2*i+1].n;//每个区间是其左右子树所能放入的人数总和
46 }
47 }
48
49 void insert(int i,int x,int m)
50 {
51 if(b[i].l==b[i].r)//找到叶子节点，这个节点存放该人，并且叶子节点能放入的人数清0
52 {
53 ans[b[i].l]=m;
54 b[i].n=0;
55 return;
56 }
57 if(x<=b[2*i].n)//其插入的位置若能放入左子树（还能放人），往左子树放人，否则走右子树
58 insert(2*i,x,m);
59 else
60 insert(2*i+1,x-b[2*i].n,m);
61 b[i].n--;
62 }
63
64 int main()
65 {
66 int i,j;
67 while(scanf("%d",&n)!=EOF)
68 {
69 for(i=1;i<=n;i++)
70 scanf("%d%d",&a[i].n,&a[i].val);
71 init();
72 for(i=n;i>0;i--)//逆推
73 {
74 insert(1,a[i].n+1,a[i].val);
75 }
76 cout<<ans[1];
77 for(i=2;i<=n;i++)
78 cout<<" "<<ans[i];
79 cout<<endl;
80 }
81 return 0;
82 }