上一节我们学习了splay所能解决的基本问题,这节我来讲一下splay怎么搞区间问题
splay搞区间问题非常简单,比如我们要在区间l,r上搞事情,那么我们首先把l的前驱旋转到根节点
再把r的后继旋转到根节点的右儿子
那么此时根节点的右儿子的左儿子所代表的就是区间l,r
这个应该比较好理解
然后就可以像线段树的lazy标记一样,给区间l,r打上标记,延迟更新,比如区间反转的时候更新的时候直接交换左右儿子
这里有一个技巧:如果一个区间被打了两次,那么就相当于不打
所以我们用一个bool变量来储存该节点是否需要被旋转
下传函数可以这么写
inline void pushdown(int x)
{
if(tree[x].rev)
{
swap(tree[x].ch[0],tree[x].ch[1]);
tree[tree[x].ch[0]].rev^=1;
tree[tree[x].ch[1]].rev^=1;
tree[x].rev=0;
}
}
注意每次rotate的时候先下传标记