splay区间翻转

题目背景
这是一道经典的Splay模板题——文艺平衡树。

题目描述
您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1

输入输出格式
输入格式：

 

第一行为n,m n表示初始序列有n个数，这个序列依次是(1,2,⋯n−1,n) m表示翻转操作次数

接下来m行每行两个数 [l,r] 数据保证1≤l≤r≤n

 

输出格式：

 

输出一行n个数字，表示原始序列经过m次变换后的结果

 

输入输出样例
输入样例#1： 复制
5 3
1 3
1 3
1 4
输出样例#1： 复制
4 3 2 1 5
说明
n,m≤100000

查看题面

这道题目要求支持区间翻转，这是splay的典型操作。

基本思想：

只要将一棵BST每一个节点的左右子树交换，就相当于翻转次树的中序遍历

实现方法：

1. 用节点中序遍历的序号表示当前节点的下标，用key存节点的序号，经过一系列操作后中序遍历即为所求

2. 每次翻转区间【L，R】时只要将排名为L-1的点splay到根，将排名R+1的点splay到根的右节点，根的右子树的左子树的中序遍历就是【L，R】

如何将一个点splay到指定位置？

只要引入y标记，当前节点的父亲为y时跳出，就可以将x刚好splay到y的儿子

inline void splay(int x,int y){
    for(int fa;(fa=f[x])!=y;rotate(x)){
        if(f[fa]!=y){
            rotate(get(fa)==get(x)?fa:x);
        }
    }
    if(y==0){
        root=x;
    }
}

1.标记是在每一次访问到一个新的节点是就要pushdown的（改变树的结构会破坏标记区间，所以先一步下传标记）

inline void push_down(int x){
    if(x&&tag[x]){
        tag[son[x][0]]^=1;
        tag[son[x][1]]^=1;
        swap(son[x][0],son[x][1]);
        tag[x]=0;
    }
}

2.区分一个节点的排名和这个节点的值：这个节点的排名是它是当前数组中的第几个，用左儿子的size+1表示；这个节点的值是题目中输入的数字，在本题中是1~N

3.增加数字为1和N+2的两个哨兵节点+INF和-INF，因此第i个节点的下标为i+1。

4.难道交换左右子树不会破坏BST的性质吗？这就是容易混淆的一点，我们的区间操作是根据下标翻转的，用数组实现时下标就是数组地址，子树交换时，只是存储内容的改变，下标位置（树的形状）只会在旋转时改变，保证BST性质。

5.此题要求一次性插入N个节点，所以可以用线段树建树的方法O(N)建树

int init(int l,int r,int fa){
    if(l>r){
        return 0;
    }
    int mid=(l+r)>>1,cur=++sz;
    key[cur]=val[mid];
    f[cur]=fa;
    son[cur][0]=init(l,mid-1,cur);
    son[cur][1]=init(mid+1,r,cur);
    upd(cur);
    return cur;
}

完整代码

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef long long LL;
  4 const int INF=1e9+7,MAXN=1e5+5,MAXM=1e5+5;
  5 int N,M,root,sz;
  6 int key[MAXN],val[MAXN],f[MAXN],son[MAXN][2],tag[MAXN],siz[MAXN];
  7 inline void DEBUG(){
  8     printf("root=%d siz=%d
",root,sz);
  9     for(int i=1;i<=sz;i++){
 10         printf("(idx=%d	key=%d	lc=%d	rc=%d)
",i,key[i],son[i][0],son[i][1]);
 11     }
 12     puts("-------------------------------------------------------");
 13 }
 14 inline void upd(int x){
 15     if(x){
 16         siz[x]=1;
 17         if(son[x][0]){
 18             siz[x]+=siz[son[x][0]];
 19         }
 20         if(son[x][1]){
 21             siz[x]+=siz[son[x][1]];
 22         }
 23     }
 24 }
 25 inline void push_down(int x){
 26     if(x&&tag[x]){
 27         tag[son[x][0]]^=1;
 28         tag[son[x][1]]^=1;
 29         swap(son[x][0],son[x][1]);
 30         tag[x]=0;
 31     }
 32 }
 33 inline int get(int x){
 34     return x==son[f[x]][1];
 35 }
 36 inline void rotate(int x){
 37     int fa=f[x],gf=f[fa],which=get(x);
 38     son[fa][which]=son[x][which^1];
 39     f[son[fa][which]]=fa;
 40     son[x][which^1]=fa;
 41     f[fa]=x;
 42     f[x]=gf;
 43     if(gf){
 44         son[gf][son[gf][1]==fa]=x;
 45     }
 46     upd(fa);
 47     upd(x);
 48 }
 49 inline void splay(int x,int y){
 50     for(int fa;(fa=f[x])!=y;rotate(x)){
 51         if(f[fa]!=y){
 52             rotate(get(fa)==get(x)?fa:x);
 53         }
 54     }
 55     if(y==0){
 56         root=x;
 57     }
 58 }
 59 int init(int l,int r,int fa){
 60     if(l>r){
 61         return 0;
 62     }
 63     int mid=(l+r)>>1,cur=++sz;
 64     key[cur]=val[mid];
 65     f[cur]=fa;
 66     son[cur][0]=init(l,mid-1,cur);
 67     son[cur][1]=init(mid+1,r,cur);
 68     upd(cur);
 69     return cur;
 70 }
 71 inline int findx(int x){//return the index
 72     int cur=root;
 73     while(1){
 74         push_down(cur);
 75         if(son[cur][0]&&x<=siz[son[cur][0]]){
 76             cur=son[cur][0];
 77         }else{
 78             x-=siz[son[cur][0]]+1;
 79             if(!x){
 80                 return cur;
 81             }
 82             cur=son[cur][1];
 83         }
 84     }
 85 }
 86 void dfs(int x){
 87     push_down(x);
 88     if(son[x][0]){
 89         dfs(son[x][0]);
 90     }
 91     if(key[x]!=INF&&key[x]!=-INF){
 92         printf("%d ",key[x]);
 93     }
 94     if(son[x][1]){
 95         dfs(son[x][1]);
 96     }
 97 }
 98 int main(){
 99     scanf("%d%d",&N,&M);
100     for(int i=2;i<=N+1;i++){
101         val[i]=i-1;
102     }
103     val[1]=-INF;
104     val[N+2]=INF;
105     root=init(1,N+2,0);
106     for(int i=1;i<=M;i++){
107         int ii,jj;
108         scanf("%d%d",&ii,&jj);
109         int l=findx(ii),r=findx(jj+2);
110         splay(l,0);
111         splay(r,l);
112         tag[son[son[root][1]][0]]^=1;
113     }
114     dfs(root);
115     return 0;
116 }

splay区间翻转

题解