[ZJOI2006]书架

题目链接

题解

这道题一开始用的是Treap写的,死活调不出来,题解又全是指针的

然后就用splay来写,发现思路自然了许多

引用自FlierKing

平衡树,需支持五个操作:
1. 将某元素置顶:将元素旋到根,然后将左子树合并到该元素的后继
2. 将某元素置底:将元素旋到根,然后将右子树合并到该元素的前驱
3. 将某元素提前/滞后1位:直接与该元素的前驱/后继交换位置及信息
4. 询问指定元素排名:将元素旋到根,输出size-1
5. 询问指定排名元素:在树上find

数组名称 数组作用
pos 保存了编号为i的书在splay中的编号
v 保存了splay编号为i的节点对应的书的编号

代码

发表评论

电子邮件地址不会被公开。 必填项已用*标注