Pps:终于学会了伸展树的区间操作，做一个完整的总结，总结一下自己的伸展树的单点操作和区间维护，顺便给未来的自己总结复习用。
splay是一种平衡树，【平均】操作复杂度O(nlogn)。首先平衡树先是一颗二叉搜索树，刚刚开始学的时候找题hash数字的题先测板子。。。
后来那题被学长改了数据不能用平衡树测了。。。一道二分数字的题。
二叉搜索树的功能是，插入一个数字，在O(logn)的时间内找到它，并操作，插入删除等。但是可能会让二叉搜索树退化成链，复杂度达到O(n)
而平衡树就是通过一系列操作改变树的形态保存，尽可能把树的高度保持在logn，上图显然存在等价的树它不是一条链，
treap, avl, 红黑树，splay，替罪羊树。。。的各种巨巨发明的平衡方法，我选择了学splay,直接原因几个学长都用splay
而且splay相对红黑树等好写，能在ACM比赛的有限时间中改出来，而且能像线段树一样维护区间信息。
Splay不是严格平衡的，它是通过对每次操作的结点，操作后让它通过一系列旋转(zig, zag)，伸展(splay)到根。80%的操作发生在20%的数据上，我们只要让它到根，尽快的取到就可以了。虽然它还是会退化成链，但是tarjan证明过它的均摊复杂度是O(nlogn)的。
我们先实现二叉搜索树的功能，存一个数字，判断它是否存在。
那么其实我们只要在插入数字，和查找数字后把那个结点旋转到根就满足了上面的要求。
先懂思路，大概文字能看的懂就好，代码实现可以慢慢继续往下看
其实旋转是无脑的。分为两种，右旋(zig)，左旋(zag)。比如把x是它父节点的左儿子，那么它要往上走就要zig。反之就要zag
其中，x,y是节点，A,B,C可能是子树，也可以是空。左边到右边，旋转x，它是y的左儿子，就右旋转。右边到左边，y是x的右儿子就要左旋。
旋转方向的判断就判断是它父亲的左儿子还是右儿子即可。
仅仅上面的旋转是不够，Splay是需要双旋操作的。仅仅单旋的复杂度是O(n)的。
1，如果要旋转的结点x的父结点是根，那么只需要单旋。否则需要双旋转。
2，如果x和它的父节点y，同属于一种类型。这里的类型是指它们都是它父节点的右儿子，或者都是它父节点的左儿子。要先旋转y，再旋转x。
简单的解释就这样。复杂的细分就是其他巨巨博客说的zig-zig, zag-zag, zig - zag, zag-zig
静态splay，key是关键字，那里判断大小的值，cnt是key出现的次数。比如你插入两个3，只要cnt++就好了，不用插入两个值为3的结点。
father表示这个结点的父结点是谁，childs[2]表示它儿子结点是谁，_size表示这个结点的子树总共有多少结点。
静态链表建的树，root表示整颗splay的根，0一直是不用的根。sign表示我们用的空间从结构体sign+1取，而不用new出来。
重新设置结点x的结点大小，主要是在旋转，伸展的过程中需要一路update上去。
然后我的旋转函数，zig和zag可以合并。我注释那部分。像我这样比较菜的只会zig,zag分开写的顺一点。。。
我们用变量把x, y, z全记住，然后改指针就好了。拿zig为例。
第一行改变了x与B的关系。
第二行是x, y的关系，下图红线
接下来如果z存在。把x, z的关系改好。就完成了一次旋转rotate ,就和最终的右图一样了。具体x是z的左儿子还是右儿子要判断。
另外，可以注意到。rotate函数中我只update了y结点。理论上我改变了这么多结点，需要update的应该不止呀。这里其实是因为旋转完y是最低的结点。其他结点还需要继续splay。既然还需要改变，就不需要现在就急着splay。
把x结点旋转，goal是旋转后x的父节点。如果splay(x, 0)就是把x旋转到根。后面区间操作部分才需要修改goal.
if(goal == 0) root = x； 也是判断x是否旋转到根，没有旋转到根，根结点就不需要改变。在单点操作中if可以不需要直接root=x，但是区间操作中必须有。
然后我们插入数据。
然后插入一个权值为x的数字。就是普通二叉排序树的插入。注意在找到结点和没找到结点创建节点后。把该节点splay到根。
init函数请参考上文的结构体。
然后解决些问题，找根节点的前驱后继。小于根节点最大的数，和大于根节点最小的数。
找key为x的节点的排名
找排名为x的数
上面几个函数应该挺好看懂的，然后还有一个删除操作。splay的删除比较简单。他的思想是把待删除节点splay到root，删除根节点成为两颗子树，所以splay tree也有人叫分裂树。在把待删除旋转到根以后。
1，如果根节点的cnt>1，我们cnt--就结束了。
2，否则，原来的根节点必然是要丢掉的。在此条件下
1，如果左右子树都是空，那么整颗树也就空了，直接重置一颗空树。
2，左子树，或右子树右一个是空。如图，我们只要把root指向A, 原来的root丢掉，把A的father=0；
3，如果左右子树都存在。我们需要把root的前继旋转到根。因为是前继，所有结果会变成下图那样。root的左子树一点是空的。那么我们直接改变pre与root的右儿子的关系就好了。
例题：洛谷P3369 https://www.luogu.org/problemnew/show/P3369
参考代码：
#include <bits/stdc++.h> using namespace std;
typedef long long LL;
const int maxn = 5e5 + ; struct Splay_Tree { struct Node {
int father, childs[], key, cnt, _size;
inline void init() {
father = childs[] = childs[] = key = cnt = _size = ;
}
inline void init(int father, int lchild, int rchild, int key, int cnt, int sz) {
this -> father = father, childs[] = lchild, childs[] = rchild;
this -> key = key, this -> cnt = cnt, _size = sz;
}
} tre[maxn];
int sign, root; inline void init() {
sign = root = ;
} inline bool judge(int x) {
return tre[ tre[x].father ].childs[] == x;
} inline void update(int x) {
if(x) {
tre[x]._size = tre[x].cnt;
if(tre[x].childs[]) {
tre[x]._size += tre[ tre[x].childs[] ]._size;
}
if(tre[x].childs[]) {
tre[x]._size += tre[ tre[x].childs[] ]._size;
}
}
} inline void rotate(int x) {
int y = tre[x].father, z = tre[y].father, k = judge(x); //tre[y].childs[k] = tre[x].childs[!k], tre[ tre[x].childs[!k] ].father = y;
//tre[x].childs[!k] = y, tre[y].father = x;
//tre[z].childs[ tre[z].childs[1] == y ] = x, tre[x].father = z; if(k == ) { ///zig
tre[y].childs[] = tre[x].childs[], tre[ tre[x].childs[] ].father = y;
tre[x].childs[] = y, tre[y].father = x;
} else { ///zag
tre[y].childs[] = tre[x].childs[], tre[ tre[x].childs[] ].father = y;
tre[x].childs[] = y, tre[y].father = x;
}
tre[z].childs[ tre[z].childs[] == y ] = x, tre[x].father = z; update(y);
} inline void splay(int x,int goal) {
for(int father; (father = tre[x].father) != goal; rotate(x) ) {
if(tre[father].father != goal) {
rotate(judge(x) == judge(father) ? father : x);
}
}
root = x;
} inline void insert_node(int x) {
if(root == ) {
tre[++sign].init(, , , x, , );
root = sign;
return ;
}
int now = root, father = ;
while() {
if(tre[now].key == x) {
tre[now].cnt ++;
update(now), update(father);
splay(now, );
break;
}
father = now;
if(x > tre[now].key) {
now = tre[now].childs[];
} else {
now = tre[now].childs[];
}
if(now == ) {
tre[++sign].init(father, , , x, , );
if(x > tre[father].key) {
tre[father].childs[] = sign;
} else {
tre[father].childs[] = sign;
}
update(father);
splay(sign, );
break;
}
}
} inline int pre() {
int now = tre[root].childs[];
while(tre[now].childs[]) {
now = tre[now].childs[];
}
return now;
} inline int next() {
int now = tre[root].childs[];
while(tre[now].childs[]) {
now = tre[now].childs[];
}
return now;
} inline int find_rank(int x) { /// 找x的排名
int now = root, ans = ;
while() {
if(x < tre[now].key) {
now = tre[now].childs[];
}
else {
if(tre[now].childs[]) {
ans += tre[ tre[now].childs[] ]._size;
}
if(x == tre[now].key) {
splay(now, );
return ans + ;
}
ans += tre[now].cnt;
now = tre[now].childs[];
}
}
} inline int find_rankx(int x) { /// 找排名为x的数字
int now = root;
while() {
if(tre[now].childs[] && x <= tre[ tre[now].childs[] ]._size ) {
now = tre[now].childs[];
} else {
int lchild = tre[now].childs[], sum = tre[now].cnt;
if(lchild) {
sum += tre[lchild]._size;
}
if(x <= sum) {
return tre[now].key;
}
x -= sum;
now = tre[now].childs[];
}
}
} inline void del(int x) {
find_rank(x);
if(tre[root].cnt > ) {
tre[root].cnt --;
update(root);
return ;
}
if(!tre[root].childs[] && !tre[root].childs[]) {
tre[root].init();
root = ;
return ;
}
if(!tre[root].childs[]) {
int old_root = root;
root = tre[root].childs[], tre[root].father = , tre[old_root].init();
return ;
}
if(!tre[root].childs[]) {
int old_root = root;
root = tre[root].childs[], tre[root].father = , tre[old_root].init();
return ;
}
int pre_node = pre(), old_root = root;
splay(pre_node, );
tre[root].childs[] = tre[old_root].childs[];
tre[ tre[old_root].childs[] ].father = root;
tre[old_root].init();
update(root);
} inline bool find(int x) {
int now = root;
while() {
if(now == ) {
return ;
}
if(x == tre[now].key) {
splay(now, );
return ;
}
if(x > tre[now].key) {
now = tre[now].childs[];
} else {
now = tre[now].childs[];
}
}
} } S; int n, opt, x; int main() {
while(~scanf("%d",&n)) {
S.init();
for(int i = ; i <= n; i ++ ) {
scanf("%d %d",&opt, &x);
switch(opt) {
case :
S.insert_node(x);
break;
case :
S.del(x);
break;
case :
printf("%d\n",S.find_rank(x));
break;
case :
printf("%d\n",S.find_rankx(x));
break;
case :
S.insert_node(x);
printf("%d\n",S.tre[S.pre()].key);
S.del(x);
break;
case :
S.insert_node(x);
printf("%d\n",S.tre[S.next()].key);
S.del(x);
break;
}
}
}
return ;
}
splay的区间维护。
我们可以把下标作为key，插入平衡树。把L-1旋转到根，R+1旋转到根的右子树。根据平衡树的性质一点是这样的。这样区间[L,R]就到了根的右子树的左子树了。如图。
这样我们对区间的操作都可以写在节点上，还可以直接给节点打lazy标记。
我们需要给数组的n个元素开头来个-inf, 末尾来个inf，保持树的结构，然后类似线段树那样递归建树，直接就是平衡的。比较懒的一个一个insert也可以。
然后就是上面说的旋转L-1,R+1区间，然后给节点打标记了。
然后就是pushdown了，这部分初学的时候，我懵逼在了这里，尤其是为什么要swap左右节点的指针。貌似会改变平衡树的有序性。这里要自己想一想。
网上竟然没有一份代码解释了这里囧。。。
个人理解：首先我们找L,R的时候通过的是节点的size（详情看我的find函数），而不是直接找key为L的值，而key的cnt也就是节点位置重复元素都是1。我们确实不需要右儿子的key大于节点，左儿子的key小于这个性质。而我们在旋转L-1,R+1的节点后，[L,R]区间又体现为一个节点。每次都是同一个。
这里的pushdown只是延迟标记，我们要证明swap的正确性只要证明swap到底的正确性即可。
例题：洛谷P3391 只有区间翻转的例题 https://www.luogu.org/problemnew/show/P3391
参考代码：
#include <bits/stdc++.h> using namespace std;
typedef long long LL;
const int maxn = 5e5 + ;
const int inf = 1e9 + ; int n, m, arr[maxn]; struct Splay_Tree { struct Node {
int father, childs[], key, cnt, _size, rev;
inline void init() {
father = childs[] = childs[] = key = cnt = _size = rev = ;
}
inline void init(int father, int lchild, int rchild, int key, int cnt, int sz) {
this -> father = father, childs[] = lchild, childs[] = rchild;
this -> key = key, this -> cnt = cnt, _size = sz;
this -> rev = ;
}
} tre[maxn];
int sign, root; inline void init() {
sign = root = ;
} inline bool judge(int x) {
return tre[ tre[x].father ].childs[] == x;
} inline void update(int x) {
if(x) {
tre[x]._size = tre[x].cnt;
if(tre[x].childs[]) {
tre[x]._size += tre[ tre[x].childs[] ]._size;
}
if(tre[x].childs[]) {
tre[x]._size += tre[ tre[x].childs[] ]._size;
}
}
} inline void rotate(int x) { int y = tre[x].father, z = tre[y].father, k = judge(x);
pushdown(y), pushdown(x);
//tre[y].childs[k] = tre[x].childs[!k], tre[ tre[x].childs[!k] ].father = y;
//tre[x].childs[!k] = y, tre[y].father = x;
//tre[z].childs[ tre[z].childs[1] == y ] = x, tre[x].father = z;
if(k == ) {///zig
tre[y].childs[] = tre[x].childs[], tre[ tre[x].childs[] ].father = y;
tre[x].childs[] = y, tre[y].father = x;
} else { ///zag
tre[y].childs[] = tre[x].childs[], tre[ tre[x].childs[] ].father = y;
tre[x].childs[] = y, tre[y].father = x;
}
tre[z].childs[ tre[z].childs[] == y ] = x, tre[x].father = z; update(y); } inline void splay(int x,int goal) {
for(int father; (father = tre[x].father) != goal; rotate(x) ) {
if(tre[father].father != goal) {
rotate(judge(x) == judge(father) ? father : x);
}
}
if(goal == ) { root = x; }
} inline void pushdown(int x) {
if(x && tre[x].rev) {
tre[ tre[x].childs[] ].rev ^= ;
tre[ tre[x].childs[] ].rev ^= ;
swap(tre[x].childs[], tre[x].childs[]);
tre[x].rev = ;
}
} int build(int l, int r, int fa) {
if(l > r) { return ; }
int mid = (l + r) >> ;
/*
tre[++sign].init(fa, 0, 0, arr[mid], 1, 1);
tre[sign].childs[0] = build(l, mid - 1, sign);
tre[sign].childs[1] = build(mid + 1, r, sign);
update(sign);
return sign;
*/
///now是必须的，sign在递归build的过程中变化了,上面就是死循环的例子
int now = ++ sign;
tre[now].init(fa, , , arr[mid], , );
tre[now].childs[] = build(l, mid - , now);
tre[now].childs[] = build(mid + , r, now);
update(now);
return now;
} int find(int x) {
int now = root;
while() {
pushdown(now);
if(x <= tre[ tre[now].childs[] ]._size) {
now = tre[now].childs[];
} else {
x -= tre[ tre[now].childs[] ]._size + ;
if(!x) {
return now;
}
now = tre[now].childs[];
}
}
} void reverse(int x, int y) {
int L = x - , R = y + , pos;
L = find(L), R = find(R);
splay(L, );
splay(R, L);
pos = tre[root].childs[];
pos = tre[pos].childs[];
tre[pos].rev ^= ;
} inline void dfs(int now) {
pushdown(now);
if(tre[now].childs[]) { dfs(tre[now].childs[]); }
if(tre[now].key != -inf && tre[now].key != inf) {
printf("%d ", tre[now].key);
}
if(tre[now].childs[]) { dfs(tre[now].childs[]); }
} } S; int main()
{
scanf("%d %d", &n, &m);
S.init();
arr[] = -inf, arr[n + ] = inf;
for(int i = ; i <= n; i ++ ) {
arr[i + ] = i;
}
S.root = S.build(, n + , );
for(int i = ; i <= m; i ++ ) {
int x, y;
scanf("%d %d", &x, &y);
S.reverse(x + , y + );
}
S.dfs(S.root);
return ;
}