POJ 2828 线段树活用

题目大意：依次描述了一个N个人的队伍，每个人所站的序号以及他的价值，依次描述每个人的过程中，存在序号相同的人，表示该人插入到了前一个序号相同的人的前面。最后输出整个队伍的值排列情况。

这个题目确实难以想到居然可以用线段树做，之前还脑残去敲什么链表，结果发现链表这玩意儿真不是一般的垃圾，好多地方根本就无法对时间进行优化。

当然了，就算告诉了你用线段树做，可能还是会很头疼，这里涉及插队操作。。而且线段树具体是存放什么东西的呢

线段树就是为了模拟当前队伍的空位数，比如一个4人队伍，Root肯定是值为4 然后左右孩子都为 2 2 ，最底下4个孩子均为1，表示该位置还可以插入几个人

插队操作是比较蛋疼的，为了避免插队，大牛们给的神思路是从后往前遍历，原理很简单，如果是插队，那从后往前，最后一个插队的，必定是站在他插得位置，扫到前面，被插队的人，因为插队的人已经占据了线段树的一个孩子，所以被插队的人只能乖乖自己选择后面的孩子。由此，问题迎刃而解。

#include <iostream>

#include <cstdio>

#include <cstring>

#define maxn 200005

#define Lson (x<<1),l,mid

#define Rson (x<<1|1),mid+1,r

using namespace std;

int d[maxn*];

int pos[maxn],v[maxn];

int ans[maxn];

void getup(int x)

{

    d[x]=d[x<<]+d[x<<|];

}

void build (int x,int l,int r)//建树如同上面的分析，使得整棵树用来存队伍里的空位数

{

    if (l==r)

    {

        d[x]=;

        return;

    }

    int mid=(l+r)/;

    build(Lson);

    build(Rson);

    getup(x);

}

void query(int loc,int rec,int x,int l,int r)

{

    if (l==r)

    {

        d[x]--;  //找到了对应的空位，则空位数--；

        ans[l]=v[rec];//l保存了当前是队伍第几个

        return;

    }

    int mid=(l+r)/;

    if (loc<=d[x<<]) query(loc,rec,Lson);

    else

        query(loc-d[x<<],rec,Rson);//这里的比较需要注意，我之前一度弄混成比较loc和l，loc虽然代表了需要插入到队伍的位置，但也可以理解为空位数，即，假如loc=2，则可以理解为必须要有两个或者两个以上空位，否则转向右孩子，但loc值要减掉左孩子的空位值，意思就是左孩子已经提供了这么多空位。

    getup(x); //及时将空位情况更新

}

int main()

{

    int n;

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

    {

        build(,,n);

        int i,j;

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

        {

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

        }

        for (j=n; j>=; j--)

        {

            query(pos[j]+,j,,,n); //由于题目给的序号是从0开始，建树什么的，我都喜欢从1开始，故这里pos+1.

        }

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

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

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

    }

    return ;

}

巴特西

POJ 2828 线段树活用

最新文章

热门文章