C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
const int maxn = 1e5 + 10;
using namespace std;
int tot = 0,root,n,m;
struct node {
int s[2] = {0,0},rev = 0,val,p = 0,size;
}tr[maxn];
inline void pushdown(int q){ //下传懒标记,如果要翻转就直接执行翻转,然后给子节点打上翻转标记
if (tr[q].rev){
swap(tr[q].s[0],tr[q].s[1]); //对于翻转操作,其实就是将当前数左边的在区间范围内的所有数和当前数在右边的在区间范围内的所有数进行交换,然后不断递归直到只有一个节点或空节点无法翻转
tr[tr[q].s[0]].rev ^= 1;
tr[tr[q].s[1]].rev ^= 1;
tr[q].rev = 0; //清空当前节点的懒标记
}
}
inline void pushup(int q){ //更新了子节点信息后,重新更新一下子树大小
tr[q].size = tr[tr[q].s[0]].size + tr[tr[q].s[1]].size + 1;
}
inline void rotate(int u){ //旋转操作
int p = tr[u].p,pp = tr[p].p,son = tr[p].s[1] == u; // p 是 当前节点的父亲,pp是祖父节点,son表示 u 是 p 的左儿子还是右儿子
tr[pp].s[tr[pp].s[1] == p] = u; //祖父节点pp原来的指向 p 的节点切换成 u
tr[p].s[son] = tr[u].s[son ^ 1]; //父亲节点p的原来指向u的节点改成u的儿子
tr[tr[u].s[son ^ 1]].p = p; //u的儿子节点更新其父亲节点为p
tr[u].s[son ^ 1] = p; //将u的儿子节点更新成p
tr[p].p = u; //更新原父亲节点p的父亲节点为 u
tr[u].p = pp; //更新u的父亲节点为祖父节点 pp
pushup(p),pushup(u); //更新了子节点信息,所以要更新一下当前节点的size
}
inline void splay(int u,int tar){ //将旋转到tar的儿子节点
int pp,p;
while (tr[u].p ^ tar){ //如果还没转到tar的儿子节点就继续转
p = tr[u].p,pp = tr[p].p; //p为父亲节点,pp为祖父节点
if (pp ^ tar) //如果祖父节点不是 tar
(tr[p].s[0] == u)^(tr[pp].s[0] == p) ? rotate(u) : rotate(p); // 如果是折线型就旋转 u 吗, 否则旋转 p
rotate(u); // 将u旋转上去(如果是单旋就不会做pp ^ tar那里的操作)
}
if (!tar) root = u; //如果说tar == 0 说明此时u是根节点,更新一下root
}
inline void add(int x){
int q = root,p = 0;
while (q) p = q,q = tr[q].s[tr[q].val < x]; //注意这里得是 x > tr[q].val, wa了一发写成了 x < tr[q].val
q = ++tot;
tr[q].p = p,tr[p].s[tr[p].val < x] = q,tr[q].val = x;
++tr[q].size; // 初始化q的大小,而p的大小不用更新,p的大小交给后面splay里面的pushup来更新
splay(q,0);
}
inline int get(int k){
int q = root ;
while (q){
pushdown(q);
if (tr[tr[q].s[0]].size >= k) q = tr[q].s[0];
else if (tr[tr[q].s[0]].size + 1 < k ) k -= tr[tr[q].s[0]].size + 1,q = tr[q].s[1]; // 这里的写法是用左子节点 + 1 < k来判断是否能到右子树,右子树的size和左子树无关,不能用右子树的size来确定位置,除非都用右子树的size不用左子树的size
else return q;
}
return q;
}
inline void print(int root){ //中序遍历输出答案
pushdown(root);
if (tr[root].s[0]) print(tr[root].s[0]);
if (tr[root].val >= 1 && tr[root].val <= n) cout << tr[root].val << ' ';
if (tr[root].s[1]) print(tr[root].s[1]);
}
int main(){
ios::sync_with_stdio(false);
cin >> n >> m;
add(1e6),add(-1e6); //加入哨兵
for (int i = 1 ; i <= n ; ++i) add(i);
for (int i = 1,l,r ; i <= m ; ++i){
cin >> l >> r ;
l = get(l),r = get(r + 2); // 加入哨兵后第l个节点实际上存的是第l - 1个值,第r + 2个节点实际上存的是第r + 1个值
splay(l,0),splay(r,l); //这样操作完之后,r的左子树存着的将是 [l,r] 的数据,此时我们只用在左子树的根加一个懒标记就可以假定我们这个[l,r]的区间已经翻转
tr[tr[r].s[0]].rev ^= 1; //假定已经翻转了,如果到了要查值,再做实际翻转的操作
}
print(root);
return 0;
}
这样翻转后的splay本身不一定具备二叉搜索树的性质 : 左子树任意节点的值 <= 根节点,右子树任意节点的值大于根节点,但是我们这题只用了splay的若干个翻转后可以使某一个子树上的所有点都是[l,r]区间的点这个性质,并没有用到BST的性质,或者说这里的splay是针对编号,第k个数来说的,第k个数一定在k-1个数的右边,第k个数的实际数值不会影响splay操作