洛谷P3391 文艺平衡树 题解

写在前头

此篇文章是本蒟蒻第一篇题解，主要是记录自己做题的一些独特体会与见解。代码还算简洁规范，适合初学者学习。

那么，开始！ Splay？

显然这道题我们用Splay来维护， 不懂戳这儿这里默认大家都懂Splay的原理了，尤其是核心 *** 作splay。当然我们需要做出一些变化。

三个性质

不妨让我们回顾一下我们以前Splay的用法——似乎跟其它平衡树无异：维护一个有序数集，支持插入，删除，求前驱、后继，求第k大的元素，求某元素排名。这是因为，我们用Splay维护的是有序数集，即权值。

性质1

在这道题中，由于要维护区间翻转这种 *** 作，我们可以用Splay去维护序列位置，即下标。此时，对于Splay中任意一棵子树（注意是子树！！！），它都代表着原序列中一段连续的区间。并且设这段区间为[l , r]，子树根结点在原序列的下标为k，那么显然t的左子树代表了[l , k - 1]区间，右子树代表了[k + 1 , r]区间。姑且将其称作性质1吧。（是不是联想到线段树了？）

这启发我们用与建线段树类似的方法建一棵比较完美的Splay。代码如下：

//以下几个函数是写在结构体里的。
	void Build (const int &l, const int &r, int &x, const int &y = 0) {
		if (l > r) return;//注意边界条件
		fa [x = ++tot] = y;
		int mid = l + r >> 1;
		val [x] = bval [mid];
		Build (l, mid - 1, ch [x] [0], x);
		Build (mid + 1, r, ch [x] [1], x);
		push_up (x);//回溯时更新
	}

是不是很像线段树？QwQ

性质2

各位可以动手模拟一下，我们发现这颗Splay的中根序居然就是1~n，即Splay的中根序对应着原序列的下标。（其实是很显然的啦）

那么请注意：在用Splay维护序列位置时，原序列位置k上的元素就是Splay里中根序为k的结点的元素。将其称作性质2吧，那么性质2可以表述为：

a [k] = val [x] (x为Splay里中根序为k的结点）

那如何求中根序为k的结点编号呢？实际上可以参照之前维护有序数集时的Get_rank函数（求排名）来写，代码：

	int k_th (int k) {
		int x = root;
		while (1) {
			push_down (x);//这行各位可以先不管
			if (k <= siz [ch [x] [0]]) x = ch [x] [0];
			else if (k == siz [ch [x] [0]] + 1) return x;
			else k -= siz [ch [x] [0]] + 1, x = ch [x] [1];
		}
	}

另外，有了这个性质，我们就可以随时按照中根序打印出序列了

	void Print (const int &x) {
		push_down (x);
		if (ch [x] [0]) Print (ch [x] [0]);
		if (val [x]) printf ("%d ", val [x]);
		if (ch [x] [1]) Print (ch [x] [1]);
	}

性质3

这时可能就有同学要问了：你Splay不是要有事没事splay一下吗？你还能保证splay之后的Splay有这些性质吗？

额还真绕口……其实splay就是反复旋转一个指定结点到目标位置去嘛……考虑旋转 *** 作：在维护有序数集时，它保持了BST（左小右大）的性质。实际上，这是因为旋转 *** 作不会改变一棵树的中根序。
可以参考一下这张图：
可以发现，中根序均为红橙黄绿蓝。所以性质2得到保证。

至于性质1，各位参考以下这张图（跟上面那张对应的）：
可以发现区间仍是连续的。

所以性质3可以表述为：性质1与性质2与Splay的形态变化无关，恒成立。

进入正题：翻转

前面铺垫了这么多，相信接下来的理解就相对简单了。

由性质1，Splay中一棵子树对应原序列一段区间，那么区间的翻转其实也就是子树的翻转，即将根结点的左右孩子交换。当然这一 *** 作是递归进行的。

（我又来画图了QWQ）

每次都递归下去？那这又和暴力又有什么区别？我们想到一个东西：懒标记tag [x]，每次翻转某棵子树就在其根结点打个标记tag [x] ^= 1 （因为两次翻转是会抵消的！！！），如果要往下走就push_down一下就行了，跟线段树懒标记的原理差不多。
下面是push_down的代码：

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

嗯，最终问题就变成了：如何找到指定区间[l , r]？
Splay的优势就凸显出来了。我们先将（l - 1）splay到根去，然后再把（r + 1）splay到根的右孩子去，那么显然此时r + 1的左子树就是[l, r]了，直接在其根结点打上标记就好。代码：

	void Reverse (const int &l, const int &r) {
		splay (k_th (l));
		splay (k_th (r + 2), root);
		tag [ch [ch [root] [1]] [0]] ^= 1;
	}

另外，如果出现翻转[1 , n]。这种极端情况，我们的程序会崩掉，所以先加两个哨兵。

完整代码！！！已经结束咧！！！

#include 
using namespace std;
const int N = 1e5 + 1;
int n, m, bval [N + 3];
struct Splay {
	int tot, root;
	bool tag [N + 3];
	int siz [N + 3], val [N + 3];
	int ch [N + 3] [2], fa [N + 3];
	void Build (const int &l, const int &r, int &x, const int &y = 0) {
		if (l > r) return;
		fa [x = ++tot] = y;
		int mid = l + r >> 1;
		val [x] = bval [mid];
		Build (l, mid - 1, ch [x] [0], x);
		Build (mid + 1, r, ch [x] [1], x);
		push_up (x);
	}
	inline void rotate (const int &x) {
		int y = fa [x], z = fa [y];
		push_down (y); push_down (x);
		bool d1 = cald (y), d2 = cald (x);
		int s = ch [x] [!d2];
		if (s) fa [s] = y; fa [y] = x; fa [x] = z;
		if (z) ch [z] [d1] = x; ch [x] [!d2] = y; ch [y] [d2] = s;
		push_up (y); push_up (x);
	}
	void splay (const int &x, const int tar = 0) {
		while (fa [x] != tar) {
			if (fa [fa [x]] != tar)
				rotate (cald (x) == cald (fa [x]) ? fa [x] : x);
			rotate (x);
		}
		if (!tar) root = x;
	}
	int k_th (int k) {
		int x = root;
		while (1) {
			push_down (x);
			if (k <= siz [ch [x] [0]]) x = ch [x] [0];
			else if (k == siz [ch [x] [0]] + 1) return x;
			else k -= siz [ch [x] [0]] + 1, x = ch [x] [1];
		}
	}
	void Reverse (const int &l, const int &r) {
		splay (k_th (l));
		splay (k_th (r + 2), root);
		tag [ch [ch [root] [1]] [0]] ^= 1;
	}
	void Print (const int &x) {
		push_down (x);
		if (ch [x] [0]) Print (ch [x] [0]);
		if (val [x]) printf ("%d ", val [x]);
		if (ch [x] [1]) Print (ch [x] [1]);
	}
	inline bool cald (const int &x) {return x == ch [fa [x]] [1];}
	inline void push_up (const int &x) {siz [x] = siz [ch [x] [0]] + siz [ch [x] [1]] + 1;}
	inline void push_down (const int &x) {
		if (x && tag [x]) {
			swap (ch [x] [0], ch [x] [1]);
			if (ch [x] [0]) tag [ch [x] [0]] ^= 1;
			if (ch [x] [1]) tag [ch [x] [1]] ^= 1;
			tag [x] = false;
		}
	}
} T;
int main () {
	scanf ("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) bval [i] = i;
	T.Build (0, n + 1, T.root);
	for (int i = 1, l, r; i <= m; ++i) {
		scanf ("%d%d", &l, &r);
		T.Reverse (l, r);
	}
	T.Print (T.root);
	return 0;
}