题解 P2475 【[SCOI2008]斜堆】
其实这篇题解只是对另一篇dalao题解经由自己理解的再阐释，侵删致歉啦qwqqqqq
我们使用的方法是：根据数据把堆的形状搞出来，然后我们在这个堆里找最后一个插入的点，然后我们还原这个点插入之前的情况，然后重复此过程，我们就能得到插入序列啦。
现在问题来了，如何找到最后一个插入的点呢？
阅读题目可知，新节点的插入无论如何都是往左子树插入，所以这个节点一定是在根节点一路向左的地方。
至于左右子树交换的操作，是在插入这个节点之前就进行的，所以对这个节点在左子树这个结论没有影响。
然后这个节点要么一路插到底（没儿子），要么是在某个点停下来，使原来在这里的点成为它的左子树，所以这个点一定没有右子树。
好啦，这样我们就可以找到这个点啦。
可是这个点不唯一怎么办？
假设我们找到了点u和相对点u深度更大的点v符合我们的条件。
如果点v仍然具有左子树，那么点v一定比点u先插入。因为若是点u先插入，点v再插入时，点u会和这颗树的右子树进行一次交换，就不符合给定树的形态了。
那么如果有更多点满足上面的条件，我们就选深度最小的。
如果点v没有左子树，那么谁先插入都可以，但是题目中给定的是小根堆，而我们要求方案字典序最小，那么我们认为点u先插入。
注意，我们先记录的点其实是较后插入的点，所以此时先记录点v
好啦，代码奉上。
如果帮助到你，记得点赞哦
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int n;
int ch[100][2],fa[100],ans[100];
int main()
{
int p;
scanf("%d",&n);
memset(ch,-1,sizeof(ch));//记得初始化哦
fa[0]=-1;
for(int i=1;i<=n;i++)
{
scanf("%d",&p);
if(p<100)
{
ch[p][0]=i;
fa[i]=p;
}
else
{
ch[p-100][1]=i;
fa[i]=p-100;
}
}
int rt=0,del,pos;//根，要删的点，指向的位置。
for(int i=0;i<=n;i++)
{
pos=rt;//从根开始找
del=-1;//没找到删除位置
while(del==-1)//还没找到可删的呢
{
if(ch[pos][1]==-1) del=pos;//莫得右儿子
pos=ch[pos][0];
}
if(ch[del][0]!=-1&&ch[ch[del][0]][0]==-1) del=ch[del][0];//字典序大的后删除
ans[i]=del;
if(del==rt) rt=ch[rt][0];//此时一定没有右儿子所以直接赋值就好啦qwq
else//做删除的逆向操作，把这个堆还原回去啦qwq
{
ch[fa[del]][0]=ch[del][0];
if(ch[del][0]!=-1) fa[ch[del][0]]=fa[del];
pos=fa[del];
while(pos!=-1)
{
swap(ch[pos][0],ch[pos][1]);
pos=fa[pos];
}
}
}
for(int i=n;i>=0;i--) printf("%d ",ans[i]);
return 0;
}