用非旋 Treap 区间翻转

Posted on | In

非旋 Treap，是一种好写，常数小，可拓展性强的弱平衡的二叉搜索树。

非旋 Treap 的讲解在其他地方也能找到，这里主要讲她的其他用法，比如——序列操作。

例题 文艺平衡树

我们来试试拿 非旋 Treap 解决 Splay 模板题~

题意

给你一个长度为 $n$ 的序列，初始值为 $(1,2,\cdots,n-1,n)$，你需要执行 $m$ 次操作，每次操作给定一个区间 $[l,r]$，你需要翻转这个区间。举个例子，序列 $(1,2,3,4,5)$ 的 $[2,5]$ 翻转后会变为：$(1,5,4,3,2)$。

$1\leqslant n,m\leqslant 10^5$。

思路

翻转的时候用一种“翻转懒标记”的东西来翻转，标记下传的时候就交换一下左右儿子，每次翻转区间 $[l,r]$ 就将原区间分成 $[1,l)$，$[l,r]$，$(r, n]$ 三部分，然后将中间那部分标记一下，最后 merge 到一起。

时间复杂度期望 $\Theta((n+m)\log n)$，空间复杂度 $\Theta(n)$。

具体细节见代码部分。

代码

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include <cstdio>
#include <random>
#include <tuple>

template <typename type, int SIZE = 100000, int seed = 19260817>
class fhq_treap {
private:
	class node {
	public:
		int key, size, lchild, rchild; 
		// key是随机权值，size是子树大小，lchild,rchild是左右儿子编号。
		type data;
		// 数据。
		bool reverse;
		// 区间翻转lazy tag
	} tree[SIZE];
	int count = 0;
	std::mt19937 myrand; // [1-3]
	
	void update_size(const int& x) { // 更新子树大小
		tree[x].size = tree[tree[x].lchild].size + tree[tree[x].rchild].size +
					   1;
		return;
	}
	
	void push_down_reverse(const int& x) {
		if (tree[x].reverse) {
			tree[x].lchild ^= tree[x].rchild ^= 
							  tree[x].lchild ^= tree[x].rchild; // swap [4]
			if (tree[x].lchild) { // 我们当然不想让tree[0]改来改去（虽然没有影响）
				tree[tree[x].lchild].reverse ^= 1; // [5]
			}
			if (tree[x].rchild) {
				tree[tree[x].rchild].reverse ^= 1;
			}
			tree[x].reverse = false;
		}
		return;
	}
	
public:
	fhq_treap(void) {
		std::mt19937 tmp(seed); // 初始化种子
		myrand = tmp;
	}
	
	int build(const int& x) { // build一个结点
		++count;
		tree[count].data = x;
		tree[count].size = 1;
		tree[count].key = myrand(); // 随机赋权值
		return count;
	}
	
	int merge(const int& x, const int& y) { // 返回x,y的子树合并后根的编号
		if (x == 0 || y == 0) { // 如果两棵树有空树
			return x + y; // 如果两棵树都是空树，返回空树，否则返回非空的那棵树
		}
		if (tree[x].key < tree[y].key) { // 如果x的随机权值比y小
			push_down_reverse(x);
			tree[x].rchild = merge(tree[x].rchild, y); // y和x右子树合并
			update_size(x); // 更新x子树大小
			return x; // 合并后x肯定为根
		}
		else { // 同上
			push_down_reverse(y);
			tree[y].lchild = merge(x, tree[y].lchild);
			update_size(y);
			return y;
		}
	}
	
	// 关于tuple的知识，你可以去 [6-7] 查看。
	std::tuple<int, int> split(const int& root, const int& k) {
		if (root == 0) {
			return std::make_tuple(0, 0);
		}
		push_down_reverse(root);
		
		std::tuple<int, int> res;
		if (tree[tree[root].lchild].size < k) { // 左子树大小不够
			auto oldres = split(tree[root].rchild,
								k - tree[tree[root].lchild].size - 1);
			// 后一个参数的意思是去掉左子树和根的大小
			tree[root].rchild = std::get<0>(oldres); // 更新右子树
			res = std::make_tuple(root, std::get<1>(oldres));
		}
		else { // 左子树大小够
			auto oldres = split(tree[root].lchild, k);
			tree[root].lchild = std::get<1>(oldres);
			res = std::make_tuple(std::get<0>(oldres), root);
		}
		update_size(root); // 更新子树大小
		return res;
	}
	
	void print(const int& root) { // 中序遍历输出整棵树
		if (root == 0) { // 如果是空树，返回。
			return;
		}
		push_down_reverse(root); // 翻转懒标记下传
		print(tree[root].lchild); // 输出左子树
		std::printf("%d ", tree[root].data); // 输出本身
		print(tree[root].rchild); // 输出右子树
		return;
	}
	
	void reverse(const int& root) { // 翻转子树
		tree[root].reverse ^= 1; // 标记一下
		return; // 搞定~
	}
};

fhq_treap<int, 100010> tree;

int main(int argc, char** argv) {
	int n, m;
	std::scanf("%d%d", &n, &m);
	
	int root = 0; // 树根
	for (int i = 1; i <= n; ++i) {
		root = tree.merge(root, tree.build(i)); // 插入i
	}
	
	for (int i = 0; i < m; ++i) {
		int revl, revr; // 翻转区间左右端点
		std::scanf("%d%d", &revl, &revr);
		auto tmp = tree.split(root, revl - 1); // 拆分-1
		auto tmp2 = tree.split(std::get<1>(tmp), revr - revl + 1); // 拆分-2
		tree.reverse(std::get<0>(tmp2)); // 翻转
		root = tree.merge(std::get<0>(tmp), tree.merge(std::get<0>(tmp2),
													   std::get<1>(tmp2))); 
		// 合并
	}
	
	tree.print(root); // 输出
	return 0;
}

// Tips:
// [1]: https://oi-wiki.org/misc/random/
// [2]: https://zh.cppreference.com/w/cpp/numeric/random/mersenne_twister_engine
// [3]: https://en.wikipedia.org/wiki/Mersenne_twister
// [4]: 第一次见这种写法，你可能会被吓到：a ^= b ^= a ^= b真的能交换a和b的值？
//		这里将阐述这种做法的正确性。我们假设x和y分别是两个bool变量，
//		如果x ^= y ^= x ^= y能交换x和y的值，那我们对a和b的每一位拿出来做这个运算，
//		也能交换这两位，于是a和b的每一位都交换了，所以a和b的值也交换了。
//		我们枚举(x, y)的4种初始值(0, 0), (0, 1), (1, 0), (1, 1)，
//		观察在x ^= y ^= x ^= y的每一步之后(x, y)的变化情况（注意^=是右结合的）：
//		(0, 0) -> (0, 0) -> (0, 0) -> (0, 0)
//		(0, 1) -> (1, 1) -> (1, 0) -> (1, 0)
//		(1, 0) -> (1, 0) -> (1, 1) -> (0, 1)
//		(1, 1) -> (0, 1) -> (0, 1) -> (1, 1)
//		发现了吗？(x, y)经过操作之后一定会变为(y, x)。所以我们证明了该操作的正确性。
// [5]: 对于bool变量x，x ^= 1等价于x = !x。
//		你可以通过枚举x分别为true和false的情况来证明这个操作的正确性。
// [6]: https://zh.cppreference.com/w/cpp/header/tuple
// [7]: https://zh.cppreference.com/w/cpp/utility/tuple