线段树单点更新poj 2828

n个人

他要插入的位置 和权值(这东西就最后输出来的)

倒的插就一定是他自己的位子

一个线段树维护一下就可以了

nlog(n)

#include<stdio.h>
#include<algorithm>

using namespace std;
#define MAXN 200010
int z[MAXN],w[MAXN],ans[MAXN];

struct node
{
    int l,r,si;
}x[MAXN<<2];

void Build(int l,int r,int a)
{
    x[a].l=l;
    x[a].r=r;
    x[a].si=r-l+1;
    if(l==r)
        return ;
    int mid=(l+r)>>1;
    Build(l,mid,a<<1);
    Build(mid+1,r,a<<1|1);
}

void Insert(int l,int r,int a1,int b1,int a)
{
    if(l==r)
    {
        ans[l]=b1;
        x[a].si--;
        return ;
    }
    int mid=(l+r)>>1;
    if(a1<=x[a<<1].si)
        Insert(l,mid,a1,b1,a<<1);
    else
        Insert(mid+1,r,a1-x[a<<1].si,b1,a<<1|1);
    x[a].si--;
}

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i++)
            scanf("%d%d",&z[i],&w[i]);
        Build(1,n,1);
        for(int i=n;i>=1;i--)
            Insert(1,n,z[i]+1,w[i],1);
        for(int i=1;i<n;i++)
            printf("%d ",ans[i]);
        printf("%d
",ans[n]);
    }
    return 0;
}