POJ 2828 Buy Tickets（线段树的单点更新）

偏执的太偏执、 2022-06-12 14:23 149阅读 0赞

*Railway tickets were difficult to buy around the Lunar New Year in China, so we must get up early and join a long queue…*

The Lunar New Year was approaching, but unluckily the Little Cat still had schedules going here and there. Now, he had to travel by train to Mianyang, Sichuan Province for the winter camp selection of the national team of Olympiad in Informatics.

It was one o’clock a.m. and dark outside. Chill wind from the northwest did not scare off the people in the queue. The cold night gave the Little Cat a shiver. Why not find a problem to think about? That was none the less better than freezing to death!

People kept jumping the queue. Since it was too dark around, such moves would not be discovered even by the people adjacent to the queue-jumpers. “If every person in the queue is assigned an integral value and all the information about those who have jumped the queue and where they stand after queue-jumping is given, can I find out the final order of people in the queue?” Thought the Little Cat.

Input

There will be several test cases in the input. Each test case consists of *N* \+ 1 lines where *N* (1 ≤ *N* ≤ 200,000) is given in the first line of the test case. The next *N* lines contain the pairs of values *Posi* and *Vali* in the increasing order of *i*(1 ≤ *i* ≤ *N*). For each *i*, the ranges and meanings of *Posi* and *Vali* are as follows:

*  *Posi* ∈ \[0, *i* − 1\] — The *i*\-th person came to the queue and stood right behind the *Posi*\-th person in the queue. The booking office was considered the 0th person and the person at the front of the queue was considered the first person in the queue.
 *  *Vali* ∈ \[0, 32767\] — The *i*\-th person was assigned the value *Vali*.

There no blank lines between test cases. Proceed to the end of input.

Output

For each test cases, output a single line of space-separated integers which are the values of people in the order they stand in the queue.

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.

![b9016c4cbefd63dba96b117b503374d9_v_1500739128][]

题解：

这题理解意思就理解了很久。。题意就是插队，共有n个人，接下来输入插队的位置和该人代表的数值，最后输出整个队伍

一开始用树状数组做，答案是对的就是TLE了，一搜原来如果要用树状数组的话就要用二分。。这个不太会写就放弃了

然后就用线段树写了。。也写了好久。。我还是太弱了，思路就是从后往前插入，便于处理我们把插入位置pos全部+1，这时插入的pos就代表该位置前面（包括该位置）需要多少个空位。。然后就是线段树找空位大法了，找到符合条件的空位就插入，这里寻找插入位置的同时可以完成更新

代码：

#include<iostream>
    #include<stdio.h>
    #include<map>
    #include<algorithm>
    #include<math.h>
    #include<queue>
    #include<stack>
    #include<string>
    #include<cstring>
    using namespace std;
    struct node
    {
        int p,v;
    }b[200005];//用于倒序存储
    struct tree
    {
        int l,r;
        int s;//记录空位数目
    }t[200005*4];
    int a[200005],n;
    void Build(int l,int r,int k)
    {
        t[k].l=l;
        t[k].r=r;
        t[k].s=r-l+1;//初始化最大
        if(l==r)
        {
            return;
        }
        int mid=(l+r)/2;
        Build(l,mid,k*2);
        Build(mid+1,r,k*2+1);
    }
    int update(int x,int k)//查找位置的同时更新空位情况
    {
        t[k].s--;
        if(t[k].l==t[k].r)//返回插入位置
        {
            return t[k].l;
        }
        int mid=(t[k].l+t[k].r)/2;
        if(x<=t[k*2].s)//左子树空位足够
        {
            return update(x,k*2);
        }
        else
        {
            x-=t[k*2].s;//不足，减去可以提供的空位后去右子树寻找空位
            return update(x,k*2+1);
        }
    }
    int main()
    {
        int i,j,m,x,y;
        while(scanf("%d",&n)!=EOF)
        {
            for(i=n-1;i>=0;i--)
            {
                scanf("%d%d",&b[i].p,&b[i].v);
                b[i].p++;
            }
            Build(1,n,1);
            for(i=0;i<n;i++)
            {
                int x=update(b[i].p,1);
                a[x]=b[i].v;
            }
            printf("%d",a[1]);
            for(i=2;i<=n;i++)
            {
                printf(" %d",a[i]);
            }
            printf("\n");
        }
        return 0;
    }

[b9016c4cbefd63dba96b117b503374d9_v_1500739128]: https://odzkskevi.qnssl.com/b9016c4cbefd63dba96b117b503374d9?v=1500739128