SGU 155 (피리 칼 나무의 구조)

제목:http://acm.sgu.ru/problem.php?contest=0&problem=155
 
제목: 각 점 의 두 값 키 와 fix 를 제시 하고 모든 키 값 과 fix 값 이 다 르 기 때문에 피리 칼 트 리 를 구성 해 야 합 니 다.각 점 의 두 개의 권 리 를 입력 하 다.
값, 피리 칼 트 리 의 각 노드 (입력 한 순서대로 번호) 의 아버지 노드 와 두 아들 의 번 호 를 출력 합 니 다.
 
분석: 우선 피리 칼 트 리 는 키 에 게 이 진 트 리 이 고 fix 에 있어 서 가장 작은 더미 이기 때문에 Treap 과 같다.피리 칼 트 리 는 LCA 와 RMQ 문제 중 에
중요 한 응용 을 하고 있다.이 문 제 는 각 노드 의 ID 를 먼저 기록 한 다음 키 를 키워드 로 정렬 합 니 다.배열 이 끝나 면 선형 구조 피리 칼 트 리 의 알고리즘 이 생 길 것 이다.
이곳 의 피리 칼 나 무 는 분명 존재 하 니 YES 를 먼저 출력 하 세 요.
 
피리 칼 나 무 를 만 드 는 과정:
데이터 구조 스 택 을 사용 합 니 다. 스 택 에 저 장 된 것 은 오른쪽 체인 입 니 다. 즉, 뿌리 결산 점 의 오른쪽 아들, 뿌리 결산 점 의 오른쪽 아들 입 니 다.
창고 꼭대기 에서 창고 밑 까지 키 를 순서대로 줄 입 니 다.
만약 에 뒤에서 앞 까지 의 순서에 따라 하나의 요소 가 a [i] 보다 큰 지 판단 하면 매번 삽입 하 는 시간 복잡 도 는 O (k + 1) 이 고 k 는 이번 삽입 에서 제거 하 는 오른쪽 체인 요소 이다.
세다모든 요소 가 오른쪽 체인 에 최대 한 번 씩 들 어가 기 때문에 전체 과정의 시간 복잡 도 는 O (n) 이다.

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

using namespace std;

const int N=1000005;
const int INF=~0U>>1;

struct node
{
    int id;        //id       ， 1  
    int key,fix;   //   
    int pre,l,r;   //           ，       
    void clear()
    {
        pre=l=r=0;
    }
    bool operator < (node t) const
    {
        return key<t.key;
    }
};

node T[N];

int stack[N],p[N],top;

void Init(int n)
{
    for(int i=1; i<=n; i++)
        T[i].pre=T[i].l=T[i].r=0;
    T[0].fix=-INF;
}

int Build(int n)
{
    top=0;
    stack[++top]=1;
    for(int i=2; i<=n; i++)
    {
        while(top>=0&&T[i].fix<T[stack[top]].fix)
            --top;
        if(top)
        {
            T[i].pre=stack[top];
            T[i].l=T[stack[top]].r;
            T[T[stack[top]].r].pre=i;
            T[stack[top]].r=i;
            stack[++top]=i;
        }
        else
        {
            T[stack[1]].pre=i;
            T[i].l=stack[1];
            stack[++top]=i;
        }
    }
    return stack[1];
}

int main()
{
    int n;
    scanf("%d",&n);
    Init(n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d%d",&T[i].key,&T[i].fix);
        T[i].id=i;
    }
    sort(T+1,T+n+1);
    int root=Build(n);
    for(int i=1; i<=n; i++)
        p[T[i].id]=i;
    puts("YES");
    for(int i=1; i<=n; i++)
        printf("%d %d %d
",T[T[p[i]].pre].id,T[T[p[i]].l].id,T[T[p[i]].r].id);
    return 0;
}