初识Splay树

yyb大佬的入门讲解：http://www.cnblogs.com/cjyyb/p/7499020.html

Orz

我就补充一下Splay树怎么作为区间树使用：

1、Splay树作为一种二叉排序树，对其中序dfs遍历后的结果便是按key值从小到大排序的数列，那么我们将编号作为key值即可。

2、如果要获取到[l,r]区间的数列，则利用Splay操作将l-1作为根，r+1作为根的右节点，再对r+1的左子树中序遍历。

3、上面似乎并没有体现区间树的效率优势。。

4、模仿线段树的做法，每个节点除了维护自身的信息外，还需维护以自己为根的这棵树对应的区间的信息，维护的信息会在rotate操作时发生改变，则在rotate操作时更新节点的信息。

5、lazy_tag，在节点信息变更或查询时，记得提前把lazy_tag下传。

洛谷的区间翻转裸题：

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstdlib>
  4 #include<cstring>
  5 #include<cmath>
  6 #include<algorithm>
  7 #include<map>
  8 using namespace std;
  9 #define N 100005
 10 struct Node{
 11     int ch[2]; //左右儿子
 12     int val;
 13     int ff;
 14     int size;
 15     int tag; 
 16 }node[N];
 17 int tot=1,root=0;
 18 inline void push_up(int x)  //refresh
 19 {    int lson=node[x].ch[0];
 20     int rson=node[x].ch[1];
 21     node[x].size=node[lson].size+node[rson].size+1;
 22 }
 23 inline void push_down(int x) //down lazy_tag
 24 {    if(node[x].tag)
 25     {
 26     node[x].tag=0;
 27     int lson=node[x].ch[0];
 28     int rson=node[x].ch[1];
 29     node[lson].tag^=1;
 30     node[rson].tag^=1;
 31     swap(node[x].ch[0],node[x].ch[1]);
 32     }
 33 }
 34 inline void rotate1(int x)
 35 {
 36     int y=node[x].ff;
 37     int z=node[y].ff;
 38     int k=(node[y].ch[1]==x);
 39     node[z].ch[node[z].ch[1]==y]=x;
 40     node[x].ff=z;
 41     
 42     node[y].ch[k]=node[x].ch[k^1];
 43     node[node[x].ch[k^1]].ff=y;
 44     
 45     node[x].ch[k^1]=y;
 46     node[y].ff=x;
 47     push_up(y);
 48     push_up(x);
 49 }
 50 inline void splay(int x,int goal) //把x节点伸展到goal节点下 
 51 {
 52     while(node[x].ff!=goal)
 53     {
 54         int y=node[x].ff;
 55         int z=node[y].ff;
 56         if(z!=goal)
 57             (node[y].ch[0]==x)^(node[z].ch[0]==y)?rotate1(x):rotate1(y);
 58         rotate1(x);
 59     }
 60     if(goal==0)root=x;
 61 }
 62 inline void ins(int v)
 63 {
 64     int u=root,ff=0;
 65     while(u&&node[u].val!=v)
 66     {    ff=u;
 67         u=node[u].ch[v>node[u].val];
 68     }
 69     if(u) ;
 70     else
 71     {
 72         u=tot++;
 73         node[ff].ch[v>node[ff].val]=u;
 74         node[u].ff=ff;
 75         node[u].ch[0]=node[u].ch[1]=0;
 76         node[u].val=v;
 77         node[u].size=1;
 78     }
 79     splay(u,0);
 80 }
 81 inline int find_k(int k)
 82 {    int u=root;
 83     while(u)
 84     {    push_down(u);
 85         int lson=node[u].ch[0];
 86         if(node[lson].size==k-1) return u;
 87         if(node[lson].size<k-1)
 88         {
 89             u=node[u].ch[1];
 90             k-=node[lson].size+1;
 91         }
 92         else
 93         {
 94             u=node[u].ch[0];
 95         }
 96     }
 97     return -1;
 98 }
 99 int n,m,a[N],tt=0;
100 void dfs_w(int x)
101 {    if(!x) return;
102     push_down(x);
103     dfs_w(node[x].ch[0]);
104     a[tt++]=node[x].val;
105     dfs_w(node[x].ch[1]);    
106 }
107 int main()
108 {
109     
110     cin>>n>>m;
111     for(int i=1;i<=n+2;i++)  //增加头尾两个哨兵 
112     {
113         ins(i);
114     }
115     while(m--)
116     {
117         int l,r;
118         scanf("%d%d",&l,&r);
119         l=find_k(l);
120         r=find_k(r+2);
121         splay(l,0);
122         splay(r,l);
123         node[node[r].ch[0]].tag^=1;
124     }
125     dfs_w(root);
126     for(int i=1;i<n;i++)
127         printf("%d ",a[i]-1);
128     printf("%d
",a[n]-1);
129     
130     return 0;
131 }