题解 P1377 【[TJOI2011]树的序】

· · 题解

喵~

稍微详细一点的说一下吧，就是楼下的两种方法的补充。

先化简一下模型，我们把BST树建好，然后输出中序遍历即是答案。

然而，直接建BST是很容易退化成链的。

做过题目多的人可能听说过，这个叫笛卡尔树

笛卡尔树是一种既满足堆性质又满足二叉排序树性质的树。

方法一：普通笛卡尔树的建树方法

现在有一个序列按二叉排序树的关键字Key从小到大有序，序列中包含小跟堆的关键字Index关键字，在O(N)的时间建树。

按原数列顺序一个一个将节点加入笛卡尔树，可以确定一定是从链的右边向下找到一个Index大于这个点的节点，把这个节点位置占据，然后置让Ta当自己的左儿子即可。

用栈把最右边的链存下来，栈顶为右边最底的那个点，加入时边弹出边向上找，更新好位置关系后把自己存进栈即可。

code：

#include <cstdio>
#include <algorithm>
#define ls t[now].ch[0]
#define rs t[now].ch[1]
#define f t[now].par
const int N=100010;
struct node
{
    int dat,index;
    bool friend operator <(node n1,node n2)
    {
        return n1.dat<n2.dat;
    }
}a[N];
struct BST
{
    int ch[2],dat,index,par;//左右儿子，BST域，堆域，父亲
}t[N];
int tot=0,n,s[N];
void connect(int fa,int now,int typ)
{
    f=fa;
    t[fa].ch[typ]=now;
}
void dfs(int now)
{
    if(!now) return;
    printf("%d ",t[now].dat);
    dfs(ls);
    dfs(rs);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",a+i);
        a[i].index=i;
    }
    std::sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)
    {
        int last=0;
        while(tot&&t[s[tot]].index>a[i].index)
            last=tot--;
        t[i].dat=a[i].dat;
        t[i].index=a[i].index;
        connect(s[tot],i,1);
        connect(i,s[last],0);
        s[++tot]=i;
    }
    dfs(t[0].ch[1]);
    return 0;
}

方法二：按堆性质自底向上建立。

这个方法好厉害啊。

则如果两个点的Key在“当前”数值上的差最小，那么Ta俩一定有一条边。

按Index从大到小建立笛卡尔树，则对1-Index-1的点中，是不会有Index的儿子的。

用pre[i]与suc[i]分别存储Key为i的点在“当前”所相邻的前驱和后继。

每次处理完一个点，更新与它相连的“前驱”和“后继”，这对应了“当前”

注意到原数据为1到n的排列，可以用桶排，比较快。

Code：

#include <cstdio>
const int N=100010;
int a[N],b[N],L[N],R[N],pre[N],suc[N],n;
void dfs(int now)
{
    if(!now) return;
    printf("%d ",a[now]);
    dfs(L[now]);dfs(R[now]);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",a+i);
        b[a[i]]=i;
        pre[i]=i-1,suc[i]=i+1;
    }
    for(int i=n;i>1;i--)
    {
        int pree=pre[a[i]],succ=suc[a[i]];
        if(b[pree]>b[succ])
            R[b[pree]]=i;
        else
            L[b[succ]]=i;
        suc[pree]=succ;pre[succ]=pree;
    }
    dfs(1);
    return 0;
}