poj 2828 线段树

http://poj.org/problem?id=2828

学到的思维：

1、变化的或者后来的优先影响前面的，那么从最后一个往前看，最后一个就成了 确定的， 而且后来的也能够确定----假设从前往后，全部的随时都不是确定的

2、线段树叶子节点直接维护区间（线段）信息，非叶子节点v维护的是以v为树根的整个子树的信息，那么假设父节点rt信息为[l,r]那么左子树维护[l,mid],右子树维护[mid+1,r]的信息。假设假设是前缀和，rt里是1-n的和，左子树1~n/2的和，右子树是n/2+1~n的和，

3、前两点想明确之后就能1A了

cnt是当前结点l~r中全部空位，这时候，认真想会发现，输入中的“次序的值”能够当做空位的个数，更新的时候，依据左右子树中的空位树有没有达到要插入的值的"次叙数"，就能够确定进入左子树或者右子树。

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

const int MAXN = 200000 +10;

int num[MAXN],pos[MAXN],ans[MAXN];

struct Node{

    int l,r;

    int cnt;//r前面还有几个空位,最初l,l+1...r-1

}nodes[MAXN*4];

void build(int rt, int l, int r)

{

    nodes[rt].l=l;

    nodes[rt].r=r;

    nodes[rt].cnt=r-l+1;

    if(l == r)

    {

        ans[l]=0;//

        return;

    }

    int mid=(l+r)/2;

    build(rt*2, l,mid);

    build(rt*2+1, mid+1, r);

}

void update(int rt, int p, int v)

{

    nodes[rt].cnt--;

    if(nodes[rt].l == nodes[rt].r)

    {

        //nodes[rt].cnt--;

        ans[nodes[rt].l]=v;

        return ;

    }

    if(p<=nodes[rt*2].cnt)update(rt*2, p, v);

    else update(rt*2+1, p-nodes[rt*2].cnt, v);

    nodes[rt].cnt=nodes[rt*2].cnt+nodes[rt*2+1].cnt;

}

int main()

{

    //freopen("poj2828.txt","r",stdin);

    int n;

    while(~scanf("%d",&n))

    {

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

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

        build(1,1,n);

        for(int i=n;i>0;i--)

        {

            update(1,pos[i]+1,num[i]);

        }

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

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

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

    }

    return 0;

}