题目大意：依次描述了一个N个人的队伍，每个人所站的序号以及他的价值，依次描述每个人的过程中，存在序号相同的人，表示该人插入到了前一个序号相同的人的前面。最后输出整个队伍的值排列情况。
这个题目确实难以想到居然可以用线段树做，之前还脑残去敲什么链表，结果发现链表这玩意儿真不是一般的垃圾，好多地方根本就无法对时间进行优化。
当然了，就算告诉了你用线段树做，可能还是会很头疼，这里涉及插队操作。。而且线段树具体是存放什么东西的呢
线段树就是为了模拟当前队伍的空位数，比如一个4人队伍，Root肯定是值为4 然后左右孩子都为 2 2 ，最底下4个孩子均为1，表示该位置还可以插入几个人
插队操作是比较蛋疼的，为了避免插队，大牛们给的神思路是从后往前遍历，原理很简单，如果是插队，那从后往前，最后一个插队的，必定是站在他插得位置，扫到前面，被插队的人，因为插队的人已经占据了线段树的一个孩子，所以被插队的人只能乖乖自己选择后面的孩子。由此，问题迎刃而解。
#include <iostream> #include <cstdio> #include <cstring> #define maxn 200005 #define Lson (x<<1),l,mid #define Rson (x<<1|1),mid+1,r using namespace std; int d[maxn*3]; int pos[maxn],v[maxn]; int ans[maxn]; void getup(int x) { d[x]=d[x<<1]+d[x<<1|1]; } void build (int x,int l,int r)//建树如同上面的分析，使得整棵树用来存队伍里的空位数 { if (l==r) { d[x]=1; return; } int mid=(l+r)/2; build(Lson); build(Rson); getup(x); } void query(int loc,int rec,int x,int l,int r) { if (l==r) { d[x]--; //找到了对应的空位，则空位数--； ans[l]=v[rec];//l保存了当前是队伍第几个 return; } int mid=(l+r)/2; if (loc<=d[x<<1]) query(loc,rec,Lson); else query(loc-d[x<<1],rec,Rson);//这里的比较需要注意，我之前一度弄混成比较loc和l，loc虽然代表了需要插入到队伍的位置，但也可以理解为空位数，即，假如loc=2，则可以理解为必须要有两个或者两个以上空位，否则转向右孩子，但loc值要减掉左孩子的空位值，意思就是左孩子已经提供了这么多空位。 getup(x); //及时将空位情况更新 } int main() { int n; while (scanf("%d",&n)!=EOF) { build(1,1,n); int i,j; for (i=1; i<=n; i++) { scanf("%d %d",&pos[i],&v[i]); } for (j=n; j>=1; j--) { query(pos[j]+1,j,1,1,n); //由于题目给的序号是从0开始，建树什么的，我都喜欢从1开始，故这里pos+1. } for (i=1; i<n; i++) printf("%d ",ans[i]); printf("%d ",ans[n]); } return 0; }