Post 18

Veröffentlicht am | Edited on

从不依靠，从不寻找，非常沉默，非常骄傲。

Splay区间翻转

显然在Post 17Splay基本操作讲清楚了，又有如下几个问题

  • 求x的前驱其实就是求x的左子树的最右边的一个结点，后继是求x的右子树的左边一个结点（想一想为什么？）

答案非常简单，如果我们把x先插入旋转到根上，左子树全部不大于x，右子树全部不小于x，左子树最右边节点保证在左子树内最大，右子树最左边节点同理。不大于x的最大值与不小于x的最小值就是前驱后继的定义（不过有可能重复）。

  • 为什么Splay提取一个区间是将区间左端点的前驱旋转至根，右端点后继旋转至根的右儿子，右儿子的左子树就是区间呢？

这个问题非常重要，是区间操作的基本原理。

显然第一次旋转后左端点在根的右子树，第二次旋转后右端点在根的右儿子的左子树，在区间(L,R)内，任何一个节点既不能在根的左子树（BST性质，它们大于左端点），又不能在根的右儿子的右子树（同样不能大于右端点），因此整个闭区间所有节点都在根的右儿子的左子树内了！

  • 还有个我认为非常难证明的问题，就是为什么懒标记是正确的。。。线段树懒标记正确在于它的形态是不会发生改变的，显然每个节点代表了固定的区间。但是Splay显然作为子树的根的节点只是临时的，那会不会造成错误的标记呢？

这个问题让我想了半天。实际上是这样的。考虑暴力Splay翻转区间是从根的右儿子的左儿子u开始，对于每个节点我们都交换左右子树，这相当于一组操作。显然只要我们没有访问一个点，它的子树交不交换并没有什么区别。也就是说我们没必要重复交换，只需要在访问的时候确保进行操作并下传标记即可。那么对于当前根，我们交换子树并给这个点打上标记，后面只要访问到这个点就下推标记并操作，这样确保每个该翻转的子树翻转了，也能优化复杂度（具体严格复杂度证明以后补上吧）。

总结一下这个问题就是：只要子树不旋转，这个子树的根就不pushdown，这其实就是懒标记的思想，尽管Splay不像线段树形态固定，只要遵循这一原则就一定不会出错。

上述问题都理解了的话，一遍写过Splay十分轻松（97行）

那么区间操作也不是很难了，我们只需要在提取的区间根节点交换左右儿子并打上懒标记即可。

献上我自己靠理解写的小常数Splay (⊙o⊙)。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 500005
#define INF 0x7ffffff
#define ls s[node][0]
#define rs s[node][1] 
int f[maxn] , s[maxn][2] , key[maxn] , val[maxn] , n , m , sz[maxn] , rev[maxn] , tot, root;
inline void update(int node)
{
	if(node){
		sz[node] = 1;
		sz[node] += sz[ls];
		sz[node] += sz[rs];
	}
}
inline void pushdown(int node)
{
	if(node && rev[node])
	{
		rev[node] = 0;
		rev[ls] ^= 1;
		rev[rs] ^= 1;
		std::swap(ls , rs);
	}
}
inline int get(int node){
	return s[f[node]][1] == node;
}
inline void rotate(int node)
{
	int fx = f[node] , ffx = f[fx] , son = get(node);
	s[fx][son] = s[node][son^1] , f[s[node][son^1]] = fx;
	f[node] = ffx ;
   	if(ffx)	s[ffx][s[ffx][1]==fx] = node;
	s[node][son^1] = fx , f[fx] = node;
	update(node) , update(fx) ;
}
inline void splay(int x , int pos)
{
	for(int fx ; (fx = f[x]) != pos ; rotate(x))
		if(f[fx] != pos)
			rotate((get(x) == get(fx))? fx : x);
	if(!pos) root = x;
}
int build(int l , int r , int fx)
{
	if(l > r) return 0;
	int mid = l + r >> 1 , node = ++tot;
	key[node] = val[mid];
	f[node] = fx;
	ls = build(l , mid - 1 , node);
	rs = build(mid + 1 , r , node);
	update(node);
	return node;
}
int find(int k)
{
	int node = root;
	while(node)
	{
		pushdown(node);
		if(k <= sz[ls]) node = ls;
		else{
			k -= sz[ls] + 1;
			if(!k) return node;
			node = rs;
		}
	}
	return -1;
}
void print(int node)
{
	pushdown(node);
	if(ls) print(ls);
	if(key[node] != -INF && key[node] != INF) printf("%d ",key[node]);
	if(rs) print(rs);
}
int main()
{
	scanf("%d%d",&n,&m);
	val[1] = -INF , val[n+2] = INF;
	for(int i = 2 ; i <= n + 1 ; ++i)
		val[i] = i-1;
	root = build(1 , n + 2 , 0);
	while(~(--m))
	{
		int l , r;
		scanf("%d%d",&l,&r);
		int posl = find(l) , posr = find(r+2);
		splay(posl , 0);
		splay(posr , posl);
		rev[s[s[root][1]][0]] ^= 1;
	}
	print(root);
}

接下来就继续学习进阶指南了。

感觉动力有点不足