poj 2828 Buy Tickets(动态队列·线段树单点更新)

题目：​​http://poj.org/problem?id=2828​​

大意：一群人排队，第i个人来到队伍中站到处于posi的人的右边，且每个人都有不同的表示值，问最终的结果？

Sample Input

4
0 77
1 51
1 33
2 69
4
0 20523
1 19243
1 3890
0 31492

Sample Output

77 33 69 51
31492 20523 3890 19243

Hint

The figure below shows how the Little Cat found out the final order of people in the queue described in the first test case of the sample input.

能力低，感觉自己还得好好加油啊。。初读这题，感觉很厉害的样子，果然，想了很久还是没得到结果。参考了大神们的思路，总算有点头绪了。正确排序的关键是后来的有位置上的优先权：所以从后向前输入，用一颗二叉树的叶子节点来放各个点。pos决定初始位置，在二叉树中寻找叶子节点即可，如果pos没有空余的位置了就向后放（右子树）。起初我怀疑过这种方法，比如：

考虑从后往前输入，第一个例子：

0 0 69 0

0 33 69 0

0 33 69 51

77 33 69 51

但是第二个例子：

31492 0 0 0

31492 3890 0 0

31492 3890 19243 0

31492 3890 19243 20523

这不是和结果不符吗？但还好可以进一步用pos和num的关系来决定位置，详见代码：

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=2e5+5;
int ans[maxn];
struct node{
int l,r,num;
int mid(){ return (l+r)/2; }
}tree[maxn<<2];
void build(int root,int low,int high){
tree[root].l=low;
tree[root].r=high;
if(low==high){
tree[root].num=1;
return ;
}
int m=tree[root].mid();
build(2*root,low,m); //no if else
build(2*root+1,m+1,high);
tree[root].num=tree[2*root].num+tree[2*root+1].num;
}
void insert(int root,int p,int val){
if(tree[root].l==tree[root].r){
//cout<<tree[root].l<<endl;
tree[root].num=0;
ans[tree[root].l]=val;
return ;
}
if(p<=tree[2*root].num)
insert(2*root,p,val);
else {
p=p-tree[2*root].num; //pos有一个作用：测试num，pos-num变成右子树的测试num
insert(2*root+1,p,val); //eg.p=3,left_num=1,for right_tree: p=2
} //if p=3,left_tree is full,left_num=0, find suitable place in right_tree.
tree[root].num=tree[2*root].num+tree[2*root+1].num;
}
struct tnode{
int pos,val;
}tp[maxn];
int main()
{
//freopen("cin.txt","r",stdin);
int n;
while(cin>>n){
build(1,1,n);
for(int i=0;i<n;i++){
scanf("%d%d",&tp[i].pos,&tp[i].val);
}
//for(int i=7;i>=1;i--)cout<<tree[i].num<<" "; cout<<endl;
for(int i=n-1;i>=0;i--){
insert(1,tp[i].pos+1,tp[i].val);
}
//for(int i=7;i>=1;i--)cout<<tree[i].num<<" "; cout<<endl;
for(int i=1;i<n;i++){
printf("%d ",ans[i]);
}
printf("%d\n",ans[n]);
}
return 0;
}