首页 > > 程序设计 > C/C++ >

【阶梯报告】洛谷P3391【模板】文艺平衡树 splay

2018-11-20 03:15:14来源：博客园阅读 ()

题目链接在这里[链接](https://www.luogu.org/problemnew/show/P3391)
最近在学习splay，终于做对了这道模版题，虽然不是很难的样子。~~但是我一开始并不会做，而且看完题解之后还打错一直打不对，调试了很久~~
下面是题目简述

现在给你一个长度为n的序列，序列元素初始为1,2,3...n，同时有m个操作，每个操作给定一个L和R，表示将[L,R]区间的数进行翻转。
输出：完成所有操作之后的序列（n,m≤100000）

首先，这道题用暴力是肯定超时的。但是既然连题目都提示用splay做这道题了，那么我们自然可以用splay做这道题。
首先我们想一下splay的树的性质。
### 性质
1. 如果我们给每一个点添加一个键值，这个键值表示的是这个点在序列中的位置，那么我们对splay树进行中序遍历之后，得到的序列就是原来对应的序列。
2. 对于splay树，无论是进行zip还是zap操作，都不会影响最终中序遍历的结果。因为zip和zap都是在保证二叉查找树的性质的前提下进行的。
3. 假如我们splay(L-1,root),然后，splay(R+1,root->right_child),那么我们就会惊奇地发现，区间[L,R]内的所有点都在R+1这个结点的左子树种。
4. 假如我们把任意一个结点的子树中的每一个结点的左右子树都换边，（包括自己）那么最终中序遍历的结果就是——除了被翻转的子树以外，其他所有点的中序遍历都没有变化，而子树中的所有节点（包括子树根节点）的中序遍历刚刚好反了过来。（你们可以自己画一个图试一下，或者说，如下图）

思路
第一种简陋的想法
1. 以1,2,3,4...n为键值插入splay树（或者直接构建一棵平衡树就行，因为你已经知道会有哪些元素插入树中）。之后，我们对树的所有操作都不需要用到键值，直接根据zip和zap不会改变中序遍历的特性进行改变。
2. 翻转区间的时候，先splay(l-1,root),splay(r+1,root->right_child)，然后再把r+1这个结点的左子树的所有左右孩子交换即可。

虽然这么做确实可以做对题目，但是这样会有几个需要注意的地方。
1 . 假如要reserve(1,n),那么我们将会splay(0,root)和splay(n+1,root->left_child),但是树中没有0和n+1这两个结点。因此一开始的时候我们就应该加入INF和-INF，充当卫兵的作用。
2 . 交换子树中所有结点的速度实在是太慢了，和o(n)压根没有区别。这样根本就没有变快。
优化的方法
1. 翻转树的时候不需要把整个子树都交换，只要采取线段树的懒标记的方法做一个标记即可。
- 标记完之后，假如等一下再标记同样的区间，只要异或一下1就可以了
- 假如要splay的点在已经翻转过的子树里面，那么我们到时候只要在寻找结点的过程中进行push_down就可以了。
- 在输出整棵splay树的时候，也注意一下push_down就可以了。
具体方法
1. 把所有的元素都塞进splay里面。由于一开始就是有序的，所以你既可以一个一个地insert进去，也可以直接就构建一个十分平衡的splay树
2. 对于每一个翻转操作，首先splay(l-1,root),splay(r+1,root->right_child),然后再把r+1的左子树打上标记即可
3. 要点：每次在find一个结点的时候，一定要先push_down,然后再进行操作。
4. 最后输出整棵树的时候也注意一下push_down
下面是我的代码，可能不是很看得明白。

  1 #include<cstdio>
  2 using namespace std;
  3 const int N=100010;
  4 const int INF=100000000;
  5 struct node
  6 {
  7 int lc,rc,fa,size,val,mark;//mark就是懒标记，val是本来的值,size是子树（包括自己）的大小 
  8 node()
  9 {
 10 lc=rc=fa=size=val=mark=0;
 11 }
 12 }tree[N];
 13 int root=1,tot=1,FIRST=1;
 14 void build(int,int,int,int);//直接用递归在刚开始的时候建立一棵比较平衡的树 
 15 void push_down(int);
 16 void zip(int);//左旋 
 17 void zap(int);//右旋
 18 void initailize();//放入INT和-INF作为卫兵 
 19 void splay(int,int);
 20 int find(int);//用于寻找splay树中的第几大的数。毕竟在序列中排第k的数就是在splay中第k大的数 
 21 void reverse(int,int);
 22 void print(int);//用递归输出整棵树 
 23 int main()
 24 {
 25 int n,m;
 26 scanf("%d%d",&n,&m);
 27 build(1,1,n,0);
 28 initailize();
 29 while(m--)
 30 {
 31 int l,r;
 32 scanf("%d%d",&l,&r);
 33 reverse(l+1,r+1);//由于有-INF的存在，所以翻转[l,r]区间的时候，其实是翻转[l+1,r+1]区间 
 34 }
 35 print(root);
 36 return 0;
 37 }
 38 void build(int x,int l,int r,int father)
 39 {
 40 tree[x].fa=father;
 41 tree[x].size=1;
 42 if(l==r)
 43 {
 44 tree[x].val=l;
 45 return;
 46 }
 47 int mid=(l+r)/2;
 48 tree[x].val=mid;
 49 if(mid==l)
 50 {
 51 tree[x].rc=++tot;
 52 build(tot,r,r,x);
 53 tree[x].size+=tree[tree[x].rc].size;
 54 }
 55 else
 56 {
 57 tree[x].lc=++tot;
 58 build(tot,l,mid-1,x);
 59 tree[x].rc=++tot;
 60 build(tot,mid+1,r,x);
 61 tree[x].size+=tree[tree[x].lc].size+tree[tree[x].rc].size;
 62 }
 63 }
 64 void initailize()
 65 {
 66 int p=root;
 67 while(tree[p].lc!=0) tree[p].size++,p=tree[p].lc;
 68 tree[p].size++;
 69 tree[p].lc=++tot;
 70 tree[tot].fa=p;
 71 tree[tot].size=1;
 72 tree[tot].val=-INF;
 73 p=root;
 74 while(tree[p].rc!=0) tree[p].size++,p=tree[p].rc;
 75 tree[p].size++;
 76 tree[p].rc=++tot;
 77 tree[tot].fa=p;
 78 tree[tot].size=1;
 79 tree[tot].val=INF;
 80 }
 81 void inline push_down(int x)
 82 {
 83 if(tree[x].mark)
 84 {
 85 int L=tree[x].lc,R=tree[x].rc;
 86 tree[L].mark^=1;
 87 tree[R].mark^=1;
 88 tree[x].mark=0;
 89 tree[x].lc=R;
 90 tree[x].rc=L;
 91 }
 92 }
 93 void zip(int x)
 94 {
 95 int y=tree[x].fa;
 96 tree[y].rc=tree[x].lc;
 97 tree[x].lc=y;
 98 tree[x].fa=tree[y].fa;
 99 tree[y].fa=x;
100 if(tree[x].fa)
101 if(tree[tree[x].fa].lc==y)
102 tree[tree[x].fa].lc=x;
103 else tree[tree[x].fa].rc=x;
104 else root=x;
105 if(tree[y].rc)
106 tree[tree[y].rc].fa=y;
107 tree[y].size=tree[tree[y].lc].size+tree[tree[y].rc].size+1;
108 tree[x].size=tree[tree[x].lc].size+tree[tree[x].rc].size+1;
109 }
110 void zap(int x)
111 {
112 int y=tree[x].fa;
113 tree[y].lc=tree[x].rc;
114 tree[x].rc=y;
115 tree[x].fa=tree[y].fa;
116 tree[y].fa=x;
117 if(tree[x].fa)
118 if(tree[tree[x].fa].lc==y)
119 tree[tree[x].fa].lc=x;
120 else tree[tree[x].fa].rc=x;
121 else root=x;
122 if(tree[y].lc)
123 tree[tree[y].lc].fa=y;
124 tree[y].size=tree[tree[y].lc].size+tree[tree[y].rc].size+1;
125 tree[x].size=tree[tree[x].lc].size+tree[tree[x].rc].size+1;
126 }
127 void splay(int x,int aim)
128 {
129 aim=tree[aim].fa;
130 while(tree[x].fa!=aim)
131 {
132 int y=tree[x].fa;
133 int z=tree[y].fa;
134 if(z==aim)
135 if(tree[y].lc==x)
136 zap(x);
137 else zip(x);
138 else if(tree[z].lc==y&&tree[y].lc==x)
139 zap(x),zap(x);
140 else if(tree[z].rc==y&&tree[y].rc==x)
141 zip(x),zip(x);
142 else if(tree[z].lc==y)
143 zip(x),zap(x);
144 else zap(x),zip(x);
145 }
146 }
147 int find(int k)
148 {
149 int p=root;
150 while(1)
151 {
152 push_down(p);
153 if(tree[tree[p].lc].size>=k)
154 p=tree[p].lc;
155 else
156 {
157 k-=tree[tree[p].lc].size;
158 if(k==1) return p;
159 k-=1;
160 p=tree[p].rc;
161 }
162 }
163 }
164 void reverse(int l,int r)
165 {
166 int L=find(l-1);
167 splay(L,root);
168 int R=find(r+1);
169 splay(R,tree[L].rc);
170 tree[tree[R].lc].mark^=1;
171 }
172 void print(int x)
173 {
174 if(x==0) return;
175 push_down(x);
176 print(tree[x].lc);
177 if(tree[x].val!=INF&&tree[x].val!=-INF)
178 {
179 if(FIRST)
180 {
181 FIRST=0;
182 printf("%d",tree[x].val);
183 }
184 else printf(" %d",tree[x].val);
185 }
186 print(tree[x].rc);
187 }