{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv\u003e \n \u003cstyle type\u003d\"text/css\"\u003e\r\n #problem-ul-reset{\r\n list-style-position: inside;\r\n list-style-type: decimal;\r\n margin: 15px;\r\n }\r\n #problem-ul-reset li { margin:5px 0; }\r\n #prog-content img { width: 55%; }\r\n\u003c/style\u003e \n \u003cdiv id\u003d\"prog-content\"\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e描述\u003c/h4\u003e \n \u003cp\u003e小Ho:小Hi,上一次你跟我讲了Treap,我也实现了。但是我遇到了一个关键的问题。\u003c/p\u003e \n \u003cp\u003e小Hi:怎么了?\u003c/p\u003e \n \u003cp\u003e小Ho:小Hi你也知道,我平时运气不太好。所以这也反映到了我写的Treap上。\u003c/p\u003e \n \u003cp\u003e小Hi:你是说你随机出来的权值不太好,从而导致结果很差么?\u003c/p\u003e \n \u003cp\u003e小Ho:就是这样,明明一样的代码,我的Treap运行结果总是不如别人。小Hi,有没有那种没有随机因素的平衡树呢?\u003c/p\u003e \n \u003cp\u003e小Hi:当然有了,这次我就跟你讲讲一种叫做Splay的树吧。而且Splay树能做到的功能比Treap要更强大哦。\u003c/p\u003e \n \u003cp\u003e小Ho:那太好了,你快告诉我吧!\u003c/p\u003e \n \u003cp\u003e\u003ca href\u003d\"#\" data-toggle\u003d\"modal\" data-target\u003d\"#m2\"\u003e提示:Splay\u003c/a\u003e\u003c/p\u003e \u003c!-- Modal --\u003e \n \u003cdiv class\u003d\"modal\" id\u003d\"m2\" tabindex\u003d\"-1\" role\u003d\"dialog\" aria-labelledby\u003d\"myModalLabel\" aria-hidden\u003d\"true\"\u003e \n \u003cdiv class\u003d\"modal-dialog\" style\u003d\"width: 870px;\"\u003e \n \u003cdiv class\u003d\"modal-content\"\u003e \n \u003cdiv class\u003d\"modal-header\"\u003e \u003cbutton type\u003d\"button\" class\u003d\"close\" data-dismiss\u003d\"modal\" aria-label\u003d\"Close\"\u003e\u003cspan aria-hidden\u003d\"true\"\u003e×\u003c/span\u003e\u003c/button\u003e \n \u003ch4 class\u003d\"modal-title\" id\u003d\"myModalLabel\"\u003e提示:Splay\u003c/h4\u003e \n \u003c/div\u003e \n \u003cdiv class\u003d\"modal-body\"\u003e \n \u003cp\u003e小Hi:Splay树,中文名一般叫做伸展树。\u003c/p\u003e \n \u003cp\u003e和Treap树相同,作为平衡树,它也是通过左旋和右旋来调整树的结构。\u003c/p\u003e \n \u003cp\u003e这里我们再复习一下左旋和右旋操作:\u003c/p\u003e \n \u003cimg src\u003d\"CDN_BASE_URL/7a8fcf8b59a560172c226ae38a248d1d?v\u003d1659770608\" title\u003d\"1.jpg\"\u003e \n \u003cp\u003e若以x作为参数(注意上一讲中是以p作为参数),其对应的伪代码分别为:\u003c/p\u003e \n \u003cpre\u003eright-rotate(x):\r\n\tp \u003d x.father\r\n\tx.father \u003d p.father\r\n\tIf (p.father is not empty) Then\r\n\t\tIf (p.father.left \u003d\u003d p) Then\r\n\t\t\tp.father.left \u003d x\r\n\t\tElse\r\n\t\t\tp.father.right \u003d x\r\n\t\tEnd If\r\n\tElse\r\n\t\troot \u003d x\r\n\tEnd If\r\n\tp.left \u003d x.right\r\n\tx.right.father \u003d p\r\n\tx.right \u003d p\r\n\tp.father \u003d x\r\n\t\r\nleft-rotate(x):\r\n\tp \u003d x.father\r\n\tx.father \u003d p.father\r\n\tIf (p.father is not empty) Then\r\n\t\tIf (p.father.left \u003d\u003d p) Then\r\n\t\t\tp.father.left \u003d x\r\n\t\tElse\r\n\t\t\tp.father.right \u003d x\r\n\t\tEnd If\r\n\tElse\r\n\t\troot \u003d x\r\n\tEnd If\r\n\tp.right \u003d x.left\r\n\tx.left.father \u003d p\r\n\tx.left \u003d p\r\n\tp.father \u003d x\u003c/pre\u003e \n \u003cp\u003e和Treap树不同的是,Splay树不再用一个随机的权值来进行平衡,而是用固定的调整方式来使得调整之后的树会比较平衡。\u003c/p\u003e \n \u003cp\u003e在左旋右旋的基础上,Splay树定义了3个操作:\u003c/p\u003e \n \u003cp\u003e1. Zig\u003c/p\u003e \n \u003cimg src\u003d\"CDN_BASE_URL/69898375133297908f68c84df831f6c8?v\u003d1659770608\" title\u003d\"2.jpg\"\u003e \n \u003cp\u003e直接根据x节点的位置,进行左旋或右旋。\u003c/p\u003e \n \u003cp\u003e该操作将x节点提升了一层。\u003c/p\u003e \n \u003cbr\u003e \n \u003cp\u003e2. Zig-Zig\u003c/p\u003e \n \u003cimg src\u003d\"CDN_BASE_URL/2737c8831fca11b5de0e50037494c0ea?v\u003d1659770608\" title\u003d\"3.jpg\"\u003e \n \u003cp\u003e若p不是根节点,还有父亲节点g,且p和x同为左儿子或右儿子,则进行Zig-Zig操作:\u003c/p\u003e \n \u003cp\u003e当x,p同为左儿子时,依次将p和x右旋;\u003c/p\u003e \n \u003cp\u003e当x,p同为右儿子时,依次将p和x左旋。\u003c/p\u003e \n \u003cp\u003e\u003cb\u003e注意此处不是将x连续Zig两次。\u003c/b\u003e该操作将x节点提升了两层。\u003c/p\u003e \n \u003cbr\u003e \n \u003cp\u003e3. Zig-Zag\u003c/p\u003e \n \u003cimg src\u003d\"CDN_BASE_URL/0592750ffdfa33fabc28266d9c749e59?v\u003d1659770608\" title\u003d\"4.jpg\"\u003e \n \u003cp\u003e若p不是根节点,则p还有父亲节点g。且p和x\u003cb\u003e不\u003c/b\u003e同为左儿子或右儿子,则进行Zig-Zag操作:\u003c/p\u003e \n \u003cp\u003e当p为左儿子,x为右儿子时,将x节点先左旋再右旋;\u003c/p\u003e \n \u003cp\u003e当p为右儿子,x为左儿子时,将x节点先右旋再左旋。\u003c/p\u003e \n \u003cp\u003e该操作将x节点提升了两层。\u003c/p\u003e \n \u003cbr\u003e \n \u003cp\u003e进一步在Zig,Zig-Zig和Zig-Zag操作上,Splay树定义了\"Splay\"操作。\u003c/p\u003e \n \u003cp\u003e对于x以及x的祖先y,splay(x, y),表示对x节点进行调整,使得x是y的儿子节点:\u003c/p\u003e \n \u003cpre\u003esplay(x, y):\r\n\tWhile (x.father !\u003d y)\r\n\t\tp \u003d x.father\r\n\t\tIf (p.father \u003d\u003d y) Then\r\n\t\t\t// 因为p的父亲是y,所以只需要将x进行Zig操作\r\n\t\t\t// 就可以使得x的父亲变为y\r\n\t\t\tIf (p.left \u003d\u003d x) Then\r\n\t\t\t\tright-rotate(x)\r\n\t\t\tElse\r\n\t\t\t\tleft-rotate(x)\r\n\t\t\tEnd If\r\n\t\tElse\r\n\t\t\tg \u003d p.father\r\n\t\t\tIf (g.left \u003d\u003d p) Then\r\n\t\t\t\tIf (p.left \u003d\u003d x) Then\r\n\t\t\t\t\t// x,p同为左儿子,Zig-Zig操作\r\n\t\t\t\t\tright-rotate(p)\r\n\t\t\t\t\tright-rotate(x)\r\n\t\t\t\tElse\r\n\t\t\t\t\t// p为左,x为右,Zig-Zag操作\r\n\t\t\t\t\tleft-rotate(x)\r\n\t\t\t\t\tright-rotate(x)\r\n\t\t\t\tEnd If\r\n\t\t\tElse\r\n\t\t\t\tIf (p.right \u003d\u003d x) Then\r\n\t\t\t\t\t// x,p同为右儿子,Zig-Zig操作\r\n\t\t\t\t\tleft-rotate(p)\r\n\t\t\t\t\tleft-rotate(x)\r\n\t\t\t\tElse \r\n\t\t\t\t\t// p为右,x为左,Zig-Zag操作\r\n\t\t\t\t\tright-rotate(x)\r\n\t\t\t\t\tleft-rotate(x)\r\n\t\t\t\tEnd If\r\n\t\t\tEnd If\r\n\t\tEnd If\r\n\tEnd While\u003c/pre\u003e \n \u003cp\u003e\u003cb\u003e在执行这个操作的时候,需要保证y节点一定是x节点祖先。\u003c/b\u003e\u003c/p\u003e \n \u003cp\u003e值得一提的是,大多数情况下我们希望通过splay操作将x旋转至整棵树的根节点。此时只需令y\u003dNULL即可实现。\u003c/p\u003e \n \u003cbr\u003e \n \u003cp\u003e小Ho:旋转和Splay我懂了,但是要怎么运用上去呢?\u003c/p\u003e \n \u003cp\u003e小Hi:Splay树的插入和查询操作和普通的二叉搜索树没有什么大的区别,需要注意的是每次插入和查询结束后,需要对访问节点做一次Splay操作,将其旋转至根。\u003c/p\u003e \n \u003cpre\u003einsert(key):\r\n\tnode \u003d bst_insert(key) // 同普通的BST插入, node为当前插入的新节点\r\n\tsplay(node, NULL)\r\n\t\r\nfind(key):\r\n\tnode \u003d bst_find(key) // 同普通的BST查找, node为查找到的节点\r\n\tsplay(node, NULL)\u003c/pre\u003e \n \u003cp\u003e同时由于Splay的特性,我们还有两个特殊的查询操作。在树中查找指定数key的前一个数和后一个数。\u003c/p\u003e \n \u003cp\u003e我们先将key旋转至根,那么key的前一个数一定是根节点左儿子的最右子孙,同时key的后一个数一定是根节点右儿子的最左子孙。\u003c/p\u003e \n \u003cpre\u003efindPrev(key):\r\n\tsplay( find(key), NULL )\r\n\tnode \u003d root.left\r\n\tWhile (node.right)\r\n\t\tnode \u003d node.right\r\n\tReturn node\r\n\t\r\n\tfindNext(key):\r\n\tsplay( find(key), NULL )\r\n\tnode \u003d root.right\r\n\tWhile (node.left)\r\n\t\tnode \u003d node.left\r\n\tReturn node\u003c/pre\u003e \n \u003cbr\u003e \n \u003cp\u003esplay中的删除key操作:\u003c/p\u003e \n \u003cp\u003esplay的删除可以采用和一般二叉搜索树相同的方法:即先找到节点key,若key没有儿子则直接删去;若key有1个儿子,则用儿子替换掉x;若key有2个儿子,则通过找到其前(或后)一个节点来替换掉它,最后将该节点Splay到根。\u003c/p\u003e \n \u003cp\u003e同时,这里还有另一种方法来完成删除操作:\u003c/p\u003e \n \u003cp\u003e首先我们查找到key的前一个数prev和后一个数next。将prev旋转至根,再将next旋转为prev的儿子。\u003c/p\u003e \n \u003cp\u003e此时key节点一定是next的左儿子。那么直接将next的左儿子节点删去即可。\u003c/p\u003e \n \u003cpre\u003edelete(key):\r\n\tprev \u003d findPrev(key)\r\n\tnext \u003d findNext(key)\r\n\tsplay(prev, NULL)\r\n\tsplay(next, prev)\r\n\tnext.left \u003d NULL\u003c/pre\u003e \n \u003cp\u003e这里你可能会担心如果key是数中最小或者是最大的数怎么办?\u003c/p\u003e \n \u003cp\u003e一个简单的处理方式是手动加入一个超级大和超级小的值作为头尾。\u003c/p\u003e \n \u003cbr\u003e \n \u003cp\u003e那么小Ho,这里有一个问题,假如要删除一个区间[a,b]的数该怎么做?\u003c/p\u003e \n \u003cp\u003e小Ho:我想想...我知道了!\u003c/p\u003e \n \u003cp\u003e因为要删除[a,b],那么我就要想办法把[a,b]的数旋转到一个子树上,再将这个子树删掉就行了。\u003c/p\u003e \n \u003cp\u003e方法和删除一个数相同,我首先将a的前一个数prev和b的后一个数next找出来。\u003c/p\u003e \n \u003cp\u003e同样将prev旋转至根,再将next旋转为prev的儿子。\u003c/p\u003e \n \u003cp\u003e那么此时next的左子树一定就是所有[a,b]之间的数了!\u003c/p\u003e \n \u003cpre\u003edeleteInterval(a, b):\r\n\tprev \u003d findPrev(a)\r\n\tnext \u003d findNext(b)\r\n\tsplay(prev, NULL)\r\n\tsplay(next, prev)\r\n\tnext.left \u003d NULL\r\n\u003c/pre\u003e \n \u003cp\u003e小Hi:没错,那么下一个问题!如果a,b不在树中呢?\u003c/p\u003e \n \u003cp\u003e小Ho:这还不简单,把a,b插入树中,做完之后再删除不就好了!\u003c/p\u003e \n \u003cp\u003e小Hi:想不到小Ho你还蛮机智的嘛。\u003c/p\u003e \n \u003cp\u003e小Ho:那是,毕竟是我小Ho。(哼哼)\u003c/p\u003e \n \u003cp\u003e小Hi:Splay树由于splay操作的使得其相较于Treap具有更大的灵活性,并且不再有随机性。其插入、查找和删除操作的均摊时间复杂度也都是O(logn)的,具体的复杂度分析可以参考\u003ca href\u003d\"https://en.wikipedia.org/wiki/Splay_tree\"\u003e这里\u003c/a\u003e。那么最后小Ho你能够把Splay的实现出来么?\u003c/p\u003e \n \u003cp\u003e小Ho:没问题,看我的吧!\u003c/p\u003e \n \u003c/div\u003e \n \u003cdiv class\u003d\"modal-footer\"\u003e \u003cbutton type\u003d\"button\" class\u003d\"btn btn-default\" data-dismiss\u003d\"modal\"\u003eClose\u003c/button\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e输入\u003c/h4\u003e \n \u003cp\u003e第1行:1个正整数n,表示操作数量,100≤n≤200,000\u003c/p\u003e \n \u003cp\u003e第2..n+1行:可能包含下面3种规则:\u003c/p\u003e \n \u003cp\u003e1个字母\u0027I\u0027,紧接着1个数字k,表示插入一个数字k到树中,1≤k≤1,000,000,000,保证每个k都不相同\u003c/p\u003e \n \u003cp\u003e1个字母\u0027Q\u0027,紧接着1个数字k。表示询问树中不超过k的最大数字\u003c/p\u003e \n \u003cp\u003e1个字母\u0027D\u0027,紧接着2个数字a,b,表示删除树中在区间[a,b]的数。\u003c/p\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e输出\u003c/h4\u003e \n \u003cp\u003e若干行:每行1个整数,表示针对询问的回答,保证一定有合法的解\u003c/p\u003e \n \u003c/div\u003e \n\u003c/div\u003e \n\u003cdt\u003e\n Sample Input \n\u003c/dt\u003e \n\u003cdd\u003e \n \u003cpre\u003e6\r\nI 1\r\nI 2\r\nI 3\r\nQ 4\r\nD 2 2\r\nQ 2\u003c/pre\u003e \n\u003c/dd\u003e \n\u003cdt\u003e\n Sample Output \n\u003c/dt\u003e \n\u003cdd\u003e \n \u003cpre\u003e3\r\n1\u003c/pre\u003e \n\u003c/dd\u003e\n\u003cdiv\u003e \n \u003cstyle type\u003d\"text/css\"\u003e\r\n #problem-ul-reset{\r\n list-style-position: inside;\r\n list-style-type: decimal;\r\n margin: 15px;\r\n }\r\n #problem-ul-reset li { margin:5px 0; }\r\n #prog-content img { width: 55%; }\r\n\u003c/style\u003e \n \u003cdiv id\u003d\"prog-content\"\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e描述\u003c/h4\u003e \n \u003cp\u003e小Ho:小Hi,上一次你跟我讲了Treap,我也实现了。但是我遇到了一个关键的问题。\u003c/p\u003e \n \u003cp\u003e小Hi:怎么了?\u003c/p\u003e \n \u003cp\u003e小Ho:小Hi你也知道,我平时运气不太好。所以这也反映到了我写的Treap上。\u003c/p\u003e \n \u003cp\u003e小Hi:你是说你随机出来的权值不太好,从而导致结果很差么?\u003c/p\u003e \n \u003cp\u003e小Ho:就是这样,明明一样的代码,我的Treap运行结果总是不如别人。小Hi,有没有那种没有随机因素的平衡树呢?\u003c/p\u003e \n \u003cp\u003e小Hi:当然有了,这次我就跟你讲讲一种叫做Splay的树吧。而且Splay树能做到的功能比Treap要更强大哦。\u003c/p\u003e \n \u003cp\u003e小Ho:那太好了,你快告诉我吧!\u003c/p\u003e \n \u003cp\u003e\u003ca href\u003d\"#\" data-toggle\u003d\"modal\" data-target\u003d\"#m2\"\u003e提示:Splay\u003c/a\u003e\u003c/p\u003e \u003c!-- Modal --\u003e \n \u003cdiv class\u003d\"modal\" id\u003d\"m2\" tabindex\u003d\"-1\" role\u003d\"dialog\" aria-labelledby\u003d\"myModalLabel\" aria-hidden\u003d\"true\"\u003e \n \u003cdiv class\u003d\"modal-dialog\" style\u003d\"width: 870px;\"\u003e \n \u003cdiv class\u003d\"modal-content\"\u003e \n \u003cdiv class\u003d\"modal-header\"\u003e \u003cbutton type\u003d\"button\" class\u003d\"close\" data-dismiss\u003d\"modal\" aria-label\u003d\"Close\"\u003e\u003cspan aria-hidden\u003d\"true\"\u003e×\u003c/span\u003e\u003c/button\u003e \n \u003ch4 class\u003d\"modal-title\" id\u003d\"myModalLabel\"\u003e提示:Splay\u003c/h4\u003e \n \u003c/div\u003e \n \u003cdiv class\u003d\"modal-body\"\u003e \n \u003cp\u003e小Hi:Splay树,中文名一般叫做伸展树。\u003c/p\u003e \n \u003cp\u003e和Treap树相同,作为平衡树,它也是通过左旋和右旋来调整树的结构。\u003c/p\u003e \n \u003cp\u003e这里我们再复习一下左旋和右旋操作:\u003c/p\u003e \n \u003cimg src\u003d\"CDN_BASE_URL/7a8fcf8b59a560172c226ae38a248d1d?v\u003d1659770608\" title\u003d\"1.jpg\"\u003e \n \u003cp\u003e若以x作为参数(注意上一讲中是以p作为参数),其对应的伪代码分别为:\u003c/p\u003e \n \u003cpre\u003eright-rotate(x):\r\n\tp \u003d x.father\r\n\tx.father \u003d p.father\r\n\tIf (p.father is not empty) Then\r\n\t\tIf (p.father.left \u003d\u003d p) Then\r\n\t\t\tp.father.left \u003d x\r\n\t\tElse\r\n\t\t\tp.father.right \u003d x\r\n\t\tEnd If\r\n\tElse\r\n\t\troot \u003d x\r\n\tEnd If\r\n\tp.left \u003d x.right\r\n\tx.right.father \u003d p\r\n\tx.right \u003d p\r\n\tp.father \u003d x\r\n\t\r\nleft-rotate(x):\r\n\tp \u003d x.father\r\n\tx.father \u003d p.father\r\n\tIf (p.father is not empty) Then\r\n\t\tIf (p.father.left \u003d\u003d p) Then\r\n\t\t\tp.father.left \u003d x\r\n\t\tElse\r\n\t\t\tp.father.right \u003d x\r\n\t\tEnd If\r\n\tElse\r\n\t\troot \u003d x\r\n\tEnd If\r\n\tp.right \u003d x.left\r\n\tx.left.father \u003d p\r\n\tx.left \u003d p\r\n\tp.father \u003d x\u003c/pre\u003e \n \u003cp\u003e和Treap树不同的是,Splay树不再用一个随机的权值来进行平衡,而是用固定的调整方式来使得调整之后的树会比较平衡。\u003c/p\u003e \n \u003cp\u003e在左旋右旋的基础上,Splay树定义了3个操作:\u003c/p\u003e \n \u003cp\u003e1. Zig\u003c/p\u003e \n \u003cimg src\u003d\"CDN_BASE_URL/69898375133297908f68c84df831f6c8?v\u003d1659770608\" title\u003d\"2.jpg\"\u003e \n \u003cp\u003e直接根据x节点的位置,进行左旋或右旋。\u003c/p\u003e \n \u003cp\u003e该操作将x节点提升了一层。\u003c/p\u003e \n \u003cbr\u003e \n \u003cp\u003e2. Zig-Zig\u003c/p\u003e \n \u003cimg src\u003d\"CDN_BASE_URL/2737c8831fca11b5de0e50037494c0ea?v\u003d1659770608\" title\u003d\"3.jpg\"\u003e \n \u003cp\u003e若p不是根节点,还有父亲节点g,且p和x同为左儿子或右儿子,则进行Zig-Zig操作:\u003c/p\u003e \n \u003cp\u003e当x,p同为左儿子时,依次将p和x右旋;\u003c/p\u003e \n \u003cp\u003e当x,p同为右儿子时,依次将p和x左旋。\u003c/p\u003e \n \u003cp\u003e\u003cb\u003e注意此处不是将x连续Zig两次。\u003c/b\u003e该操作将x节点提升了两层。\u003c/p\u003e \n \u003cbr\u003e \n \u003cp\u003e3. Zig-Zag\u003c/p\u003e \n \u003cimg src\u003d\"CDN_BASE_URL/0592750ffdfa33fabc28266d9c749e59?v\u003d1659770608\" title\u003d\"4.jpg\"\u003e \n \u003cp\u003e若p不是根节点,则p还有父亲节点g。且p和x\u003cb\u003e不\u003c/b\u003e同为左儿子或右儿子,则进行Zig-Zag操作:\u003c/p\u003e \n \u003cp\u003e当p为左儿子,x为右儿子时,将x节点先左旋再右旋;\u003c/p\u003e \n \u003cp\u003e当p为右儿子,x为左儿子时,将x节点先右旋再左旋。\u003c/p\u003e \n \u003cp\u003e该操作将x节点提升了两层。\u003c/p\u003e \n \u003cbr\u003e \n \u003cp\u003e进一步在Zig,Zig-Zig和Zig-Zag操作上,Splay树定义了\"Splay\"操作。\u003c/p\u003e \n \u003cp\u003e对于x以及x的祖先y,splay(x, y),表示对x节点进行调整,使得x是y的儿子节点:\u003c/p\u003e \n \u003cpre\u003esplay(x, y):\r\n\tWhile (x.father !\u003d y)\r\n\t\tp \u003d x.father\r\n\t\tIf (p.father \u003d\u003d y) Then\r\n\t\t\t// 因为p的父亲是y,所以只需要将x进行Zig操作\r\n\t\t\t// 就可以使得x的父亲变为y\r\n\t\t\tIf (p.left \u003d\u003d x) Then\r\n\t\t\t\tright-rotate(x)\r\n\t\t\tElse\r\n\t\t\t\tleft-rotate(x)\r\n\t\t\tEnd If\r\n\t\tElse\r\n\t\t\tg \u003d p.father\r\n\t\t\tIf (g.left \u003d\u003d p) Then\r\n\t\t\t\tIf (p.left \u003d\u003d x) Then\r\n\t\t\t\t\t// x,p同为左儿子,Zig-Zig操作\r\n\t\t\t\t\tright-rotate(p)\r\n\t\t\t\t\tright-rotate(x)\r\n\t\t\t\tElse\r\n\t\t\t\t\t// p为左,x为右,Zig-Zag操作\r\n\t\t\t\t\tleft-rotate(x)\r\n\t\t\t\t\tright-rotate(x)\r\n\t\t\t\tEnd If\r\n\t\t\tElse\r\n\t\t\t\tIf (p.right \u003d\u003d x) Then\r\n\t\t\t\t\t// x,p同为右儿子,Zig-Zig操作\r\n\t\t\t\t\tleft-rotate(p)\r\n\t\t\t\t\tleft-rotate(x)\r\n\t\t\t\tElse \r\n\t\t\t\t\t// p为右,x为左,Zig-Zag操作\r\n\t\t\t\t\tright-rotate(x)\r\n\t\t\t\t\tleft-rotate(x)\r\n\t\t\t\tEnd If\r\n\t\t\tEnd If\r\n\t\tEnd If\r\n\tEnd While\u003c/pre\u003e \n \u003cp\u003e\u003cb\u003e在执行这个操作的时候,需要保证y节点一定是x节点祖先。\u003c/b\u003e\u003c/p\u003e \n \u003cp\u003e值得一提的是,大多数情况下我们希望通过splay操作将x旋转至整棵树的根节点。此时只需令y\u003dNULL即可实现。\u003c/p\u003e \n \u003cbr\u003e \n \u003cp\u003e小Ho:旋转和Splay我懂了,但是要怎么运用上去呢?\u003c/p\u003e \n \u003cp\u003e小Hi:Splay树的插入和查询操作和普通的二叉搜索树没有什么大的区别,需要注意的是每次插入和查询结束后,需要对访问节点做一次Splay操作,将其旋转至根。\u003c/p\u003e \n \u003cpre\u003einsert(key):\r\n\tnode \u003d bst_insert(key) // 同普通的BST插入, node为当前插入的新节点\r\n\tsplay(node, NULL)\r\n\t\r\nfind(key):\r\n\tnode \u003d bst_find(key) // 同普通的BST查找, node为查找到的节点\r\n\tsplay(node, NULL)\u003c/pre\u003e \n \u003cp\u003e同时由于Splay的特性,我们还有两个特殊的查询操作。在树中查找指定数key的前一个数和后一个数。\u003c/p\u003e \n \u003cp\u003e我们先将key旋转至根,那么key的前一个数一定是根节点左儿子的最右子孙,同时key的后一个数一定是根节点右儿子的最左子孙。\u003c/p\u003e \n \u003cpre\u003efindPrev(key):\r\n\tsplay( find(key), NULL )\r\n\tnode \u003d root.left\r\n\tWhile (node.right)\r\n\t\tnode \u003d node.right\r\n\tReturn node\r\n\t\r\n\tfindNext(key):\r\n\tsplay( find(key), NULL )\r\n\tnode \u003d root.right\r\n\tWhile (node.left)\r\n\t\tnode \u003d node.left\r\n\tReturn node\u003c/pre\u003e \n \u003cbr\u003e \n \u003cp\u003esplay中的删除key操作:\u003c/p\u003e \n \u003cp\u003esplay的删除可以采用和一般二叉搜索树相同的方法:即先找到节点key,若key没有儿子则直接删去;若key有1个儿子,则用儿子替换掉x;若key有2个儿子,则通过找到其前(或后)一个节点来替换掉它,最后将该节点Splay到根。\u003c/p\u003e \n \u003cp\u003e同时,这里还有另一种方法来完成删除操作:\u003c/p\u003e \n \u003cp\u003e首先我们查找到key的前一个数prev和后一个数next。将prev旋转至根,再将next旋转为prev的儿子。\u003c/p\u003e \n \u003cp\u003e此时key节点一定是next的左儿子。那么直接将next的左儿子节点删去即可。\u003c/p\u003e \n \u003cpre\u003edelete(key):\r\n\tprev \u003d findPrev(key)\r\n\tnext \u003d findNext(key)\r\n\tsplay(prev, NULL)\r\n\tsplay(next, prev)\r\n\tnext.left \u003d NULL\u003c/pre\u003e \n \u003cp\u003e这里你可能会担心如果key是数中最小或者是最大的数怎么办?\u003c/p\u003e \n \u003cp\u003e一个简单的处理方式是手动加入一个超级大和超级小的值作为头尾。\u003c/p\u003e \n \u003cbr\u003e \n \u003cp\u003e那么小Ho,这里有一个问题,假如要删除一个区间[a,b]的数该怎么做?\u003c/p\u003e \n \u003cp\u003e小Ho:我想想...我知道了!\u003c/p\u003e \n \u003cp\u003e因为要删除[a,b],那么我就要想办法把[a,b]的数旋转到一个子树上,再将这个子树删掉就行了。\u003c/p\u003e \n \u003cp\u003e方法和删除一个数相同,我首先将a的前一个数prev和b的后一个数next找出来。\u003c/p\u003e \n \u003cp\u003e同样将prev旋转至根,再将next旋转为prev的儿子。\u003c/p\u003e \n \u003cp\u003e那么此时next的左子树一定就是所有[a,b]之间的数了!\u003c/p\u003e \n \u003cpre\u003edeleteInterval(a, b):\r\n\tprev \u003d findPrev(a)\r\n\tnext \u003d findNext(b)\r\n\tsplay(prev, NULL)\r\n\tsplay(next, prev)\r\n\tnext.left \u003d NULL\r\n\u003c/pre\u003e \n \u003cp\u003e小Hi:没错,那么下一个问题!如果a,b不在树中呢?\u003c/p\u003e \n \u003cp\u003e小Ho:这还不简单,把a,b插入树中,做完之后再删除不就好了!\u003c/p\u003e \n \u003cp\u003e小Hi:想不到小Ho你还蛮机智的嘛。\u003c/p\u003e \n \u003cp\u003e小Ho:那是,毕竟是我小Ho。(哼哼)\u003c/p\u003e \n \u003cp\u003e小Hi:Splay树由于splay操作的使得其相较于Treap具有更大的灵活性,并且不再有随机性。其插入、查找和删除操作的均摊时间复杂度也都是O(logn)的,具体的复杂度分析可以参考\u003ca href\u003d\"https://en.wikipedia.org/wiki/Splay_tree\"\u003e这里\u003c/a\u003e。那么最后小Ho你能够把Splay的实现出来么?\u003c/p\u003e \n \u003cp\u003e小Ho:没问题,看我的吧!\u003c/p\u003e \n \u003c/div\u003e \n \u003cdiv class\u003d\"modal-footer\"\u003e \u003cbutton type\u003d\"button\" class\u003d\"btn btn-default\" data-dismiss\u003d\"modal\"\u003eClose\u003c/button\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e输入\u003c/h4\u003e \n \u003cp\u003e第1行:1个正整数n,表示操作数量,100≤n≤200,000\u003c/p\u003e \n \u003cp\u003e第2..n+1行:可能包含下面3种规则:\u003c/p\u003e \n \u003cp\u003e1个字母\u0027I\u0027,紧接着1个数字k,表示插入一个数字k到树中,1≤k≤1,000,000,000,保证每个k都不相同\u003c/p\u003e \n \u003cp\u003e1个字母\u0027Q\u0027,紧接着1个数字k。表示询问树中不超过k的最大数字\u003c/p\u003e \n \u003cp\u003e1个字母\u0027D\u0027,紧接着2个数字a,b,表示删除树中在区间[a,b]的数。\u003c/p\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e输出\u003c/h4\u003e \n \u003cp\u003e若干行:每行1个整数,表示针对询问的回答,保证一定有合法的解\u003c/p\u003e \n \u003c/div\u003e \n\u003c/div\u003e \n\u003cdt\u003e\n Sample Input \n\u003c/dt\u003e \n\u003cdd\u003e \n \u003cpre\u003e6\r\nI 1\r\nI 2\r\nI 3\r\nQ 4\r\nD 2 2\r\nQ 2\u003c/pre\u003e \n\u003c/dd\u003e \n\u003cdt\u003e\n Sample Output \n\u003c/dt\u003e \n\u003cdd\u003e \n \u003cpre\u003e3\r\n1\u003c/pre\u003e \n\u003c/dd\u003e"}}]}