[SCOI2008]斜堆

贪心

题面

斜堆是一种二叉树，且每个非根结点的值都比它父亲大。
在斜堆$H$中插入新元素$X$的过程是递归进行的：

• 当$H$为空或者$X$小于$H$的根结点时,$X$变为新的树根，而原来的树根（如果有的话）变为$X$的左儿子。
• 当$X$大于$H$的根结点时，$H$根结点的两棵子树交换，而$X$（递归）插入到交换后的左子树中。

现给出一个大小为$n+1$的斜堆，询问该斜堆字典序最小的插入序列。

• $n\leq50$

解析

经过审题，我们发现每次插入元素后，该子树的根一定会有左子树，而右子树只能通过新元素经过、结点交换左右子树产生。
然后就看不出什么了？

一开始，我们不会求插入序列，但我们似乎可以求最后插入的那个元素。

• 它是极左点（即从根往下走的都是左子树）。
• 它没有右子树（因为没有新元素经过它往下走）。

于是我们可以初步确定它是极左链上的几个元素，但是并不确定他是哪一个。
对此可以讨论一下。设$x,y$为符合条件的两点，$x$深度大于$y$。

• 如果$x$是最后插入的：
  由$deep_x>deep_y$可知，$x$插入时一定经过了$y$，则$y$一定交换过左右子树。而$y$又满足最终只有右子树的性质，所以在$x$经过前，$y$只能有右子树或者没有子树。而这是不可能的。

因而可证明最后插入的点一定是极左链上深度最小的点，或者是该点的是叶结点的左儿子。
而为了保证字典序最小，如果能取后者就取。

而找出最后插入的点并把它删掉后，问题就转化为规模更小的子问题，我们可以在剩下的斜堆中找出最后插入的点，以此类推。
最后倒着输出答案即可。
时间复杂度$O(nlogn)$。。。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define re register
#define il inline
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
int n,d[100],f[100],ls[100],rs[100],ans[100],top,flag,rt=1;
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il void dfs(re int u)
{
  if(!rs[u])
    {
      if(ls[u]&&!ls[ls[u]]&&!rs[ls[u]])
    {
      ans[++top]=ls[u],flag=1;
      ls[u]=0;f[ls[u]]=0;
    }
      else
    {
      ans[++top]=u,flag=1;
      if(u==rt) rt=ls[u];
      ls[f[u]]=ls[u];f[ls[u]]=f[u];f[u]=0;
    }
    }
  if(flag) return;
  if(ls[u]) dfs(ls[u]);
  if(flag) {swap(ls[u],rs[u]);return;}
}
int main()
{
  n=gi();
  fp(i,2,n+1)
    {
      d[i]=gi();
      if(d[i]>=100) rs[d[i]-100+1]=i,f[i]=d[i]-100+1;
      else ls[d[i]+1]=i,f[i]=d[i]+1;
    }
  while(top<=n)
    {
      flag=0,dfs(rt);
    }
  fq(i,top,1) printf("%d ",ans[i]-1);puts("");
  return 0;
}