题意：有N个人排队，给出各个人想插队的位置和标识，要求输出最后的序列。
分析：因为之前的序列会因为插队而变化，如果直接算时间复杂度很高，所以可以用
线段树逆序插入，把序列都插到最后一层，len记录该区间里还剩余多少位置，插入的时候就插到剩余的第几个位置，
比如1，2已经插入了，如果再想插入第3个位置，则实际上插入的是5. 因为是逆序的，所以在3之前除了现在的1，2
还有之前的1，2.
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 const int maxn = 200000+10; 7 using namespace std; 8 int n, ans[maxn]; 9 struct node 10 { 11 int p, v; 12 }a[maxn]; 13 struct line 14 { 15 int l, r, len; //区间剩余的长度 16 }tr[4*maxn]; 17 void build(int o, int l, int r) 18 { 19 tr[o].l = l; tr[o].r = r; 20 tr[o].len = r-l+1; 21 if(l==r) return; 22 int mid = (l+r)/2; 23 build(2*o, l, mid); 24 build(2*o+1, mid+1, r); 25 } 26 void update(int o, int p, int v) 27 { 28 tr[o].len --; 29 if(tr[o].l==tr[o].r) 30 { 31 ans[tr[o].l] = v; //ans记录最后一层的值 32 return; 33 } 34 if(p<tr[2*o].len) update(2*o, p, v); 35 else update(2*o+1, p-tr[2*o].len, v); 36 } 37 int main() 38 { 39 int i; 40 while(~scanf("%d", &n)) 41 { 42 for(i = 0; i < n; i++) 43 scanf("%d%d", &a[i].p, &a[i].v); 44 build(1, 0, n-1); 45 for(i = n-1; i >= 0; i--) //逆序 46 update(1, a[i].p, a[i].v); 47 48 for(i = 0; i < n-1; i++) 49 printf("%d ", ans[i]); 50 printf("%d ", ans[i]); 51 } 52 return 0; 53 }