伸展树总结

最近做的1些Splay题及思路

BZOJ 1588 就是求1个数的先驱和后继，用Splay很简单

POJ 3468  很经典的线段树题目，用Splay做练习怠惰标记

HDU 1890  触及区间翻转，注意直接以数列下标建树，对原数列排序后，直接查找，找到后删除。

HDU 3436  很好的1道题，首先离散化，Splay 树中每一个节点表示的是1段区间，

TOP:首先删除这个元素，再将其插入到队首

RANK：即寻觅第K大，经典操作

QUERY：将该元素Splay 到根部，size[ch[root][0]]+1即是排名

HDU 3487 多了1个操作切割，常规操作

BZOJ 1269  SPLAY的1些常规操作，没甚么特殊的

BZOJ 1500 多了1个最大序列和，处理类似于线段树中的区间合并，其它是常规操作；此题需要回收内存。空姐点的值要设为-inf才正确。中间TLE 了很屡次

POJ 3580  REVOLVE 操作可以看成1次删除和1次插入，例如[a,b]向右移动T步等价于[a,b-t],[b-t+1,b];先删除[a,b-t],再将其插入到a+t后面；中间TLE 了很屡次

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠