题解 P1377 【[TJOI2011]树的序】 伸展树做法
wjyyy
2018-06-19 21:28:39
安利一下[个人博客](http://www.wjyyy.top/487.html),虽然可能排版没有这里好看……
虽然这个题正解不是平衡树,不过可以拿平衡树优化一下常数,达到$ O(NlogN)$就能过了。
### 为什么可以用平衡树呢?
**平衡树**套用了BST的一种性质,就是某数在插入前(第一个数跳过),要么它的前驱和后继的深度是不同的,要么它没有前驱(此时前驱深度定为0),要么它没有后继(此时后继深度定为0);**这时候它一定会被插入为较深的那一个的孩子**(下面给出证明)。
### 做法
因此我们只需要存每个点的节点地址,就可以用平衡树求出前驱和后继从而直接访问较深节点并插入,就回避了BST退化成链的情况。~~**用BST优化BST XD**~~
**上述命题证明:**如果遍历过程两个节点都要经过(即在根节点的同侧),那么会去到较深的点。**因为经过较浅的那个节点时,那个节点会把它继续向下插入,直到找到较深的另一个点,这是BST的插入性质。**如果遍历过程不同时经过这两个点(前驱和后继),则不会出现分属两树的情况,因为此时的根节点比前驱大,比后继小,那么前驱和后继求的就是不合法的,因此不会出现这种情况。**原命题得证。**
### 总结
伸展树在这里会用到的功能可能不算多,所以敲起来比较方便也比较迅速。因此在想不到正解而splay可做时,就最好先打个splay上去咯。(~~说不定平衡树是正解啊蛤蛤蛤~~)
### 习惯用指针
## Code:
```cpp
#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;
}
```