标签:Splay

高级数据结构【Splay相关,可持久化数据结构、重量平衡树、仙人掌系列、支配树、划分树】 Summary

huangkui 2018年3月14日 No Comments Algorithm, Problem, Summary , , , , , , ,

知识点总结 这个专题好像没什么新算法,标题里的重量平衡树、仙人掌、划分树好像都没用到。。。 都是一些可持久化数据结构和Splay的题目 最多多了一个支配树,在专门那篇Blog里也有学习资料

Luogu P2596 [ZJOI2006]书架(Splay)

huangkui 2018年1月12日 No Comments Problem , , ,

题目链接:传送门 Description 小T有一个很大的书柜。这个书柜的构造有些独特,即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。 小T在看书的时候,每次取出一本书,看完后放回书柜然后再拿下一本。由于这些书太有吸引力了,所以她看完后常常会忘记原来是放在书柜的什么位置。不过小T的记忆力是非常好的,所以每次放书的时候至少能够将那本书放在拿出来时的位置附近,比如说她拿的时候这本书上面有X本书,那么放回去时这本书上面就只可能有 […]

Luogu P3369【模板】普通平衡树(Splay板子)

huangkui 2018年1月10日 No Comments Algorithm, Problem , , ,

题目链接:传送门 Description 您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作: 插入x数 删除x数(若有多个相同的数,因只删除一个) 查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数,因输出最小的排名) 查询排名为x的数 求x的前驱(前驱定义为小于x,且最大的数) 求x的后继(后继定义为大于x,且最小的数)

Page 1 of 1