poj_2828线段树，逆序插入

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

const int maxn = 200020;

using namespace std;

int p[200020],v[200020];

int sum[maxn<<2];

int ans[maxn];

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

{

    sum[rt]=r-l+1;

    int m=(r+l)/2;

    if(l==r)

        return;

    build(lson);

    build(rson);

}

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

{

    sum[rt]--;

    int m=(r+l)/2;

    if(l==r)

    {

        ans[l]=v;

        return ;

    }

    if(sum[rt<<1]>=p)

    {

        update(v,p,lson);

    }

    else

    {

        p-=sum[rt<<1];

        update(v,p,rson);

    }

}

int main()

{

    int n;

    while(cin>>n)

    {

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

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

        build(1,n,1);

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

            update(v[i],p[i]+1,1,n,1);

        cout<<ans[1];

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

            cout<<" "<<ans[i];

        cout<<endl;

    }

    return 0;

}
巴特西

poj_2828线段树，逆序插入

最新文章

热门文章
