题解 P1377 【[TJOI2011]树的序】 伸展树做法

wjyyy

2018-06-19 21:28:39

Solution

安利一下[个人博客](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; } ```