洛谷 P1377 [TJOI2011]树的序 暴力数据结构做法 题解【树的遍历】【splay】

点击量：270

   这个题正解不是平衡树，不过可以拿平衡树优化一下常数，$ O(NlogN)$就能过了。

目录

题目描述

众所周知，二叉查找树的形态和键值的插入顺序密切相关。准确的讲：1、空树中加入一个键值k，则变为只有一个结点的二叉查找树，此结点的键值即为k；2、在非空树中插入一个键值k，若k小于其根的键值，则在其左子树中插入k，否则在其右子树中插入k。

我们将一棵二叉查找树的键值插入序列称为树的生成序列，现给出一个生成序列，求与其生成同样二叉查找树的所有生成序列中字典序最小的那个，其中，字典序关系是指对两个长度同为n的生成序列，先比较第一个插入键值，再比较第二个，依此类推。

输入输出格式

输入格式：

第一行，一个整数，n，表示二叉查找树的结点个数。第二行，有n个正整数，k1到kn，表示生成序列，简单起见，k1~kn为一个1到n的排列。

 

输出格式：

一行，n个正整数，为能够生成同样二叉查找树的所有生成序列中最小的。

输入输出样例

输入样例#1：

4

1 3 4 2

输出样例#1：

1 3 2 4

说明

对于20%的数据，n ≤ 10。

 

对于50%的数据，n ≤ 100。

 

对于100%的数据，n ≤ 100,000。

   这个题正解是$ O(N)$桶排，或者$ O(NlogN)$的快排后拿笛卡尔树$ O(N)$建树，综合复杂度$ O(NlogN)$。

   而平衡树套用了BST的一种性质，就是某数在插入前（第一个数跳过），要么它的前驱和后继的深度是不同的，要么它没有前驱（此时前驱深度定为0），要么它没有后继（此时后继深度定为0）；这时候它一定会被插入为较深的那一个的孩子（下面给出证明）。因此我们只需要存每个点的节点地址，就可以用平衡树求出前驱和后继从而直接访问较深节点并插入。

    上述命题证明：如果遍历过程两个节点都要经过（即在根节点的同侧），那么会去到较深的点。因为经过较浅的那个节点时，那个节点会把它继续向下插入，直到找到较深的另一个点，这是BST的插入性质。如果遍历过程不同时经过这两个点（前驱和后继），则不会出现分属两树的情况，因为此时的根节点比前驱大，比后继小，那么前驱和后继求的就是不合法的，因此不会出现这种情况。原命题得证。

   伸展树在这里会用到的功能不算多，所以敲起来比较方便也比较迅速。因此在想不到正解而splay可做时，就最好先打个splay上去咯。（说不定平衡树是正解啊蛤蛤蛤）

Code：

#include<cstdio>
#include<cstring>
#define Root spl::root
#define RooT BST::root
int dpt[101000];//深度
namespace spl//开两个namespace可以用两个node（起名综合症）
{
struct node
{
    int key;
    node *s[2];
    node(int key)
    {
        this->key=key;
        s[0]=NULL;
        s[1]=NULL;
    }
    node()
    {
        s[0]=NULL;
        s[1]=NULL;
    }
    int getd(int x)
    {
        if(x==key)
            return -1;
        return x>key;
    }
};
node *root=NULL;
void Rotate(node *&rt,int d)
{
    node *tmp=rt->s[d];
    rt->s[d]=tmp->s[d^1];
    tmp->s[d^1]=rt;
    rt=tmp;
    return;
}
void splay(node *&rt,int x)
{
    int d1=rt->getd(x);
    if(d1==-1)
        return;
    int d2=rt->s[d1]->getd(x);
    if(d2==-1)
    {
        Rotate(rt,d1);
        return;
    }
    splay(rt->s[d1]->s[d2],x);
    if(d1==d2)
    {
        Rotate(rt,d1);
        Rotate(rt,d1);
        return;
    }
    else
    {
        Rotate(rt->s[d1],d2);
        Rotate(rt,d1);
        return;
    }
}
void Insert(node *&rt,int x)
{
    if(!rt)
    {
        rt=new node(x);
        return;
    }
    Insert(rt->s[rt->getd(x)],x);//没有重复元素
    return;
}
//也没有删除
int getm(node *rt,int d)
{
    if(!rt->s[d])
        return rt->key;
    return getm(rt->s[d],d);
}
}
namespace BST
{
struct node
{
    int v;
    node *ls,*rs;
    node(int v)
    {
        this->v=v;
        ls=NULL;
        rs=NULL;
    }
    node()
    {
        ls=NULL;
        rs=NULL;
    }
}*root=NULL;
node *pla[101000];//存这个节点的指针地址
void Insert(node *&rt,int x,int d)//记得计算深度
{
    if(!rt)
    {
        dpt[x]=d;
        rt=new node(x);
        pla[x]=rt;
        return;
    }
    if(x<rt->v)
        Insert(rt->ls,x,d+1);
    else
        Insert(rt->rs,x,d+1);
    return;
}
void pre_ord(node *rt)
{
    printf("%d ",rt->v);
    if(rt->ls)
        pre_ord(rt->ls);
    if(rt->rs)
        pre_ord(rt->rs);
}
}
using BST::pla;

int main()
{
    memset(dpt,0,sizeof(dpt));
    memset(pla,NULL,sizeof(pla));
    int n,a;
    scanf("%d",&n);
    scanf("%d",&a);
    spl::Insert(Root,a);//第一个是构造根节点要特判
    BST::Insert(RooT,a,1);

    int p,s;//p是pre前驱，s是suc后继
    for(int i=2;i<=n;i++)
    {
        scanf("%d",&a);
        spl::Insert(Root,a);
        spl::splay(Root,a);
        p=0;//这里注意置0，否则下面用到s和p就会GG（紊乱）
        s=0;
        if(Root->s[0])
            p=getm(Root->s[0],1);
        if(Root->s[1])
            s=getm(Root->s[1],0);
        if(dpt[p]>dpt[s])
            BST::Insert(pla[p],a,1);
        else
            BST::Insert(pla[s],a,1);
    }
    BST::pre_ord(RooT);
    return 0;
}