[bzoj1078][SCOI2008]斜堆【可并堆】

【题目链接】
　　https://www.lydsy.com/JudgeOnline/problem.php?id=1078
【题解】
　　斜堆有一些有趣的性质：
　　1).最后一个插入的节点一定在最左边的一条链上。
　　2).最后一个插入的节点一定没有右儿子。
　　3).每个非叶节点都有左儿子。
　　从中，我们可以发现一个大秘密：
　　4).最后一个插入的节点一定是满足1)2)条件，且深度最小的一个。
　　证明：如果最后一个是一个更深的节点，那么由于插入时要翻转左右子树，所以浅的那一个节点会变成只有右子树的非叶节点，不满足性质2)。
　　但是有一个特例，若最浅的节点的左儿子为叶子节点，这时删了左儿子也不会违背性质，因此为了满足字典序最小，最后一个节点应该是它的左儿子。
　　从后往前依次删除堆中节点即可。
　　时间复杂度 $O (n^{2})$

/* --------------
    user Vanisher
    problem bzoj-1078 
----------------*/
# include <bits/stdc++.h>
# define    ll      long long
# define    inf     0x3f3f3f3f
# define    N       110
using namespace std;
int read(){
    int tmp=0, fh=1; char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') fh=-1; ch=getchar();}
    while (ch>='0'&&ch<='9'){tmp=tmp*10+ch-'0'; ch=getchar();}
    return tmp*fh;
}
struct node{
    int fa,pl,pr;
}T[N];
int ti,ans[N],n,rt;
void solve(int size){
    if (size==0) return;
    int x=rt;
    while (T[x].pr!=0) x=T[x].pl;
    if (T[x].pl!=0&&T[T[x].pl].pl==0)
        x=T[x].pl;
    ans[++ti]=x;
    if (T[x].fa!=-1) T[T[x].fa].pl=T[x].pl;
    if (T[x].pl!=0) T[T[x].pl].fa=T[x].fa;
    if (T[x].fa==-1) rt=T[x].pl;
    x=T[x].fa;
    while (x!=-1){
        swap(T[x].pl,T[x].pr);
        x=T[x].fa;
    }
    solve(size-1);
}
int main(){
    n=read();
    for (int i=1; i<=n; i++){
        int x=read();
        if (x>=100) 
            T[i].fa=x-100, T[x-100].pr=i;
            else T[i].fa=x, T[x].pl=i;
    }
    T[0].fa=-1;
    solve(n+1);
    for (int i=n+1; i>=1; i--)
        printf("%d ",ans[i]);
    printf("
");
    return 0;
}