POJ 2828 Buy Tickets

线段树第二题，变简单了呢，单点更新的~~~

题目大意：

有一个空队列，给出按时间顺序插队的序列，问最后这个队列里的人按什么顺序排列的。

解题思路：

线段树来做的，每个节点代表着这个节点下还有多少个空位,然后倒叙插入。更新寻找位置。

下面是代码：

#include <stdio.h>
const int Max=200005;
int node[Max<<2],num[Max];
struct node1
{
    int p,v;
} po[Max];
void build(int l,int r,int tr)
{
    node[tr]=r-l+1;
    if(l==r)return;
    int m=(l+r)>>1;
    build(l,m,tr<<1);
    build(m+1,r,tr<<1|1);
}
int query(int p,int l,int r,int tr)
{
    node[tr]--;
    if(l==r)return l;
    int m=(l+r)>>1;
    if(node[tr<<1]>=p)return query(p,l,m,tr<<1);
    else return query(p-node[tr<<1],m+1,r,tr<<1|1);
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0; i<n; i++)
        {
            scanf("%d%d",&po[i].p,&po[i].v);
        }
        build(1,n,1);
        for(int i=n-1; i>=0; i--)
        {
            num[query(po[i].p+1,1,n,1)]=po[i].v;
        }
        for(int i=1; i<n; i++)
        {
            printf("%d ",num[i]);
        }
        printf("%d\n",num[n]);
    }
    return 0;
}

POJ 2828 Buy Tickets

原文：http://blog.csdn.net/lin375691011/article/details/19555381