浅谈splay实现区间翻转
splay的功能可能比我想的要多的多。但我比较菜.所以还要慢慢学....
这里先写一个总结...其实是怕我以后忘了，关于我刚学的splay实现区间翻转...
据说splay实现区间翻转是一个很经典的应用，主要是利用的splay伸展和左右旋的性质，显然，能区间翻转的splay必然不能仍像以前那样，每个节点维护一个权值。显然会有重复，所以考虑用编号来建一颗splay。因为题目里给的是1~n的排列，所以我们可以考虑递归建树，不过我比较懒。就仍然写了一个insert....不过这都不是重点。主要的是如何实现区间翻转。那么我们很容易发现.最后的答案就是树的中序遍历。那么在翻转时，可以先找到第l大的和第r+2大的，因为防止树空，多丢进去两个数。最后输出时输出所有数的值-1即可，即掐头去尾。
重点:反转的序列必须有序
最后在根的右儿子的左儿子处打一个标记并下传。在向下遍历的时候遇到标记就交换左右儿子。因为这里节点维护的是编号，所以不需要满足二叉搜索树的性质
具体的图片解释如下：这是一个1~7的树。我们要翻转2~4这个区间
所以先把2这个节点翻转到根.根据splay旋转和伸展的规律。得到下面这样的图
然后再把6这个节点转到2的儿子 最后就是这样.虽然看起来有点丑那么我们在5这里打一个标记,所以5的左右儿子互换。最后就是这样。
然后输出中序遍历，也就是1254367 全体-1，掐头去尾，最后就是 14325，显然正确