新技能Splay

新技能Splay

平衡树这种东西很是玄学，操作倒是十分明了就是不知道为什么这么整能有一个合理的复杂度，至少我已经了解过的Treap和Splay就给我这种感觉。
大概的思想就是通过把访问的节点旋到根节点使得每条路径都多多少少发生些变化，从而防止对同一条很长的路径多次重复访问，复杂度是据说均摊的。

洛谷P3391 - 【模板】文艺平衡树

拿来测板子，但是普通平衡树之前被我用Treap过掉了，就整了个Splay特色。
对区间翻转可以先把第个节点提到根节点，再把第个节点提到根节点的右儿子，那么区间就恰好被包含在第个节点的左子树中，对这个子树打一个翻转标记就好了，之后进入这个子树时交换左右儿子即可。