zoj3765 Lights 平衡树

好吧,不得不承认,经过一个寒假的颓废啥都忘了。。
一道裸的splay,但是比赛的时候我一直觉得用splay维护gcd会不会出错。。。。因为我居然觉得旋转过程中gcd无法正确维护。。。。
思路:splay节点信息
on:节点是否是开灯状态
val0:该节点关灯时的值,如果该节点灯开着,那么val0=0,不影响结果。
val1:该节点开灯时的值,如果该节点灯关着,那么val1=0,不影响结果。
gcd0:以该节点为根的子树中所有状态为关的灯的gcd
gcd1:以该节点为根的子树中所有状态为开的灯的gcd
num[0]:以该节点为根的子树有多少个状态为关的灯
num[1]:以该节点为根的子树有多少个状态为开的灯
看来这个月要好好复习了。。。。

splay tree专题

很早以前就想学splay,但是迫于图论方面的知识还很不全面,于是放弃了计划,第一次区域赛之后打算学一下splay,所以这几天就开始看起来了,看着爽哥的ppt和模板慢慢学,到现在为止基本上理解了splay树的旋转和splay操作,然后就开始做题啦。。接下来要开始重点转入dp和数据结构的学习了~
1.关于rotate和splay操作的一个问题:为什么旋转x结点的时候只pushup()fa[x]?
答:因为rotate操作是用在splay操作里面的,由于splay的时候x结点可能被旋转多次,所以x结点为根的子树的结构在不停变化中,没必要每次旋转都pushup,但是旋转点x的父亲结点却在旋转后不会再旋转了,所以要pushupx结点的父亲。最后全部旋转完毕在pushupx结点就行了。
2.由此可能想到另一个问题:splay的时候,又是旋转x结点前要先旋转x的父节点y,这时候pushup了y的父节点z,那么y结点有没有pushup呢?
答:有的,因为每次旋转y必然伴随着旋转一次x,所以旋转x的时候,y结点pushup了。
3.要注意哪些地方要pushdown。旋转一个节点前要先pushdown父节点,再pushdownx节点,将信息下推,完成这个节点的”使命”再旋转。访问一个节点的操作之前记得pushdown,再对这个节点操作。
4.深刻理解splay树的“序”:这个序是很广义的,没有序也可以是序。加入初始插入节点完毕时其实就形成了一个“序”。这时它的中序遍历序列就是它的序,也就是说此时splay中的任意两个元素间有了一种前后关系,这就是序。splay操作会维护splay树的平衡但是不会改变这个序,也就是说splay操作之后树的中序遍历序列式不变的。
5.findpre(x)和findnext(x):这两个操作必须先把x节点splay到根。因为如果不是根,那么x的父节点有可能是所求答案,但是findpre()和findnext()并没有考虑
6.关于翻转操作