BZOJ - SpaceQ's Blog

删除操作是splay的瓶颈?(BZOJ 3224 && Tyvj 1728 普通平衡树)

 

440859 SpaceQ 3224 Wrong_Answer 3152 kb 112 ms C++/Edit 3102 B 2013-06-25 00:57:23
440857 SpaceQ 3224 Accepted 3156 kb 580 ms C++/Edit 3098 B 2013-06-25 00:54:32

上面那个不加删除,下面那个加删除。。。

删除一次要splay 两次,而且并不能降低树的高度。。。

听说splay有不可改进的常数 =3 。 2*3=6 。。。常数太大了。。。

mycode:(删除的确写丑了??)

继续阅读

Splay 终极模板!(BZOJ 1588)

写了各种Splay,以下这个版本最让我满意:)。。所以叫“终极”。。。

风格飘逸,时间短,代码短也没有恶意缩行。融合各神犇之精华。

 

46 437391(5) SpaceQ 1328 KB 136 MS C++ 1557 B 2013-06-19 23:05:14

非常满意。不加读入优化BZOJ46名。一会儿我试试读入优化的效果。

加读入优化以后

 

22 437435(6) SpaceQ 1332 KB 116 MS C++ 1888 B 2013-06-19 23:35:20

以下代码

继续阅读




Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee