POJ 2828

학대 받 는 밤 =
대 신의 블 로그 감사합니다.http://www.cnblogs.com/crazyapple/p/3233149.html
제목: 첫 줄 은 정수 N 이 고 대표 팀 은 모두 N 명 입 니 다.그리고 N 줄, 첫 번 째 숫자 가 N 을 대표 하여 팀 에 들 어 갔 을 때 앞 에 몇 명 이 있 었 고 두 번 째 숫자 는 I 개인의 식별 자 였 다.
마지막 파티 의 순서, 출력 식별 자 를 구 합 니 다.
사고방식: 사고방식 은 신의 사고방식 이 고, 내 가 또 표절 하 는 것 은 정말 수치스럽다 = =
첫 번 째 단 계 는 역순 의 사상 이다. 마지막 사람 은 앞 에 몇 개의 빈 위치 가 있어 야 하고 마지막 두 번 째 사람 은 몇 개의 빈 위치 가 있 는 지 순서대로 확정 해 야 한다.
두 번 째 단 계 는 선분 나무의 사상 에 따라 이 선분 에 몇 개의 빈 위치 가 있 는 지 기록한다.(잔 망 스 러 운 생각 은 처음에 이 라인 이전의 빈 위 치 를 기록 하 는 것 이 었 다. 분 치 를 할 때 처리 해 야 할 라인 이 너무 많 고 시간 초과 = =)
세 번 째 단 계 는 모든 사람의 최종 위 치 를 확인 하고 출력 합 니 다.(생각 은 모든 사람 이 아버지 라인 의 빈자리 수 를 갱신 하 는 동시에 아버지 라인 의 왼쪽 아들 의 빈자리 수 를 판단 하 는 것 이다. 만약 에 왼쪽 아들 의 빈자리 수가 우리 가 찾 는 위치 수 보다 크 면 왼쪽 아들 중에서 찾 아야 한다. 그렇지 않 으 면 왼쪽 아들 의 위치 수 를 뺀 후에 오른쪽 아들 에서 찾 아야 한다)

#include<iostream>

#include<stdio.h>

#include<string.h>

using namespace std;

struct tr

{

    int l,r,pos;

};

tr me[200000*3];

int shun[200001];

short his[200001];

short ans[200001];

void build(int s,int e,int k)

{

    me[k].l=s;

    me[k].r=e;

    me[k].pos=e-s+1;

    if(s==e)

        return;

    int m=(s+e)>>1;

    build(s,m,k<<1);

    build(m+1,e,k<<1|1);

}

void update(int i,int k,int c)

{

    me[k].pos--;

    if(me[k].r==me[k].l)

    {

        ans[me[k].r]=his[i];

        return;

    }

    if(me[k<<1].pos>c)

        update(i,k<<1,c);

    else

        update(i,k<<1|1,c-me[k<<1].pos);



}

int main()

{

    short tmp;

    int n,w,i;

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

    {

        memset(ans,-1,sizeof(ans));

        build(1,n,1);

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

        {

            scanf("%d%d",&shun[i],&his[i]);

        }

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

        {

            update(i,1,shun[i]);

        }

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

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

        printf("
");

    }

    return 0;

}