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

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

题目：​​Input

40 771 511 332 6940 205231 192431 38900 31492

Sample Output

77 33 69 5131492 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 #include 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<>n){ build(1,1,n); for(int i=0;i=1;i--)cout<=0;i--){ insert(1,tp[i].pos+1,tp[i].val); } //for(int i=7;i>=1;i--)cout<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。