HDU 2475 Box (splay,动态dfs序)

这题是个好题。题目大意是说桌面上有n个盒子,每个盒子都可以自由伸缩,给出盒子之间嵌套的关系,接下来有n个操作,1. 将盒子x以及盒子x内部的盒子移动到y盒子内部;2. 询问x盒子最外层的盒子是什么。

首先根据开始的嵌套关系可以建立一个森林,对每颗树建立一个splay维护一个动态的dfs序,这样插入和删除操作相当于对区间的序列进行插入删除。具体操作看代码。

PS:因为存在一棵树只有<=2个节点,有些点可能没有前驱和后继,因此学习了一种比较好的删除方法:对删除[a, b],将a splay到根,b splay到a的孩子,于是x = ch[a][0], y = ch[b][1],只要将fa[a] = fa[b] = ch[a][0] = ch[b][1] = 0,这样就讲区间[a, b]删除了,接下来只需要将b子书的最左孩子splay到根,根的ch[rt][0] = a,fa[a] = rt即可。

 

LEAVE A COMMENT