题意：人们一个一个的来排队并插队，按人到来的顺序给出每个人插队的位置（插在第几个人后面），并告知每个人的id号，输出最终队伍的情况，即最后时刻，队列中从第一个到最后一个各个人的ID号。

分析：可以用线段树，从最后来的一个人开始向来得更早的人遍历，这样pos（插在第几个人后面）的意义就变成了，前面有多少个空位。线段树上每个节点中存储的是当前时刻，该区间有多少空位。

4

0 77

1 51

1 33

2 69

排序过程是：

77

77 51

77 33 51

77 33 69 51

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

using namespace std;

#define N 200010

struct cam

{

int x,y;

int num;

}list[N*8];

int pos[N],value[N],ans[N];

int n;

void build(int k,int x,int y)  //用线段树存储区间内还有多少位子没有被占

{

list[k].x=x;

list[k].y=y;

list[k].num=(y-x+1);

if(x==y)

return;

int mid;

mid=(x+y)/2;

build(k<<1,x,mid);

build(k<<1|1,mid+1,y);

}

void find(int k,int pos,int value)//find(1,pos[i]+1,value[i]);POS[I]+1表示第I个节点放在POS[I]+1的位置

{

list[k].num--;

if(list[k].x==list[k].y)

{

ans[list[k].x]=value;//遍历到叶节点，就把该节点放入叶节点中，表示最终的位置

return;

}

if(list[k<<1].num>=pos)

/*该节点应该放在list[k]从左边开始第pos个，但是如果左边的空位POS，那么放在右边；够的话放左边.不够的原因是排队时候后面的节点排到他的前面，占用了他的位置，因此从后向前遍历，可以保证：对于处理的节点，首先看他后面节点是否已经占用了该位置，如果是，那么往后面放*/

find(k<<1,pos,value);//放在左子节点的第pos个位置

else

find(k<<1|1,pos-list[k<<1].num,value);//放在右边的时候，除去左边可以用的（空位置）

}

int main()

{

int i;

while(scanf("%d",&n)!=EOF)

{

for(i=1;i<=n;i++)

scanf("%d%d",&pos[i],&value[i]);

build(1,1,n);

for(i=n;i>=1;i--)

find(1,pos[i]+1,value[i]);

for(i=1;i<=n;i++)

{

if(i==n)

printf("%d\n",ans[i]);

else

printf("%d ",ans[i]);

}

}

return 0;

}

TreeSegment2828