此篇文章是本蒟蒻第一篇题解，主要是记录自己做题的一些独特体会与见解。代码还算简洁规范，适合初学者学习。
那么，开始！ 三个性质不妨让我们回顾一下我们以前Splay的用法——似乎跟其它平衡树无异：维护一个有序数集，支持插入，删除，求前驱、后继，求第k大的元素，求某元素排名。这是因为，我们用Splay维护的是有序数集，即权值。
性质1在这道题中，由于要维护区间翻转这种操作，我们可以用Splay去维护序列位置，即下标。此时，对于Splay中任意一棵子树（注意是子树！！！），它都代表着原序列中一段连续的区间。并且设这段区间为[l , r]，子树根结点在原序列的下标为k，那么显然t的左子树代表了[l , k - 1]区间，右子树代表了[k + 1 , r]区间。姑且将其称作性质1吧。（是不是联想到线段树了？）
这启发我们用与建线段树类似的方法建一棵大概完美的Splay。代码如下：
//以下几个函数是写在结构体里的。
void Begin () {
bval [1] = -INF;//这一行和下一行可以先不管
bval [n + 2] = INF;
for (int i = 1; i <= n; ++i) bval [i + 1] = i;
root = build (0, 1, n + 2);
}
int build (const int &y, const int &l, const int &r) {
if (l > r) return 0;//注意边界条件，不能无限递归下去
int x = ++tot;
int mid = l + r >> 1;
fa [x] = y;
val [x] = bval [mid];
ch [x] [0] = build (x, l, mid - 1);//是不是很像线段树？
ch [x] [1] = build (x, mid + 1, r);
push_up (x);
return x;
}
性质2
各位可以动手模拟一下，我们发现这颗Splay的中根序居然就是1~n，即Splay的中根序对应着原序列的下标。（其实是很显然的啦）
那么请注意：在用Splay维护序列位置时，原序列位置k上的元素就是Splay里中根序为k的结点的元素。将其称作性质2吧，那么性质2可以表述为：
a [k] = val [x] (x为Splay里中根序为k的结点）
那如何求中根序为k的结点编号呢？实际上可以参照之前维护有序数集时的Get_rank函数（求排名）来写，代码：
int find (int k) {
int x = root;
while (x) {
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] != INF && val [x] != -INF) 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]);
tag [ch [x] [0]] ^= 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 (find (l));
splay (find (r), root);
tag [ch [ch [root] [1]] [0]] ^= 1;
}
另外，如果出现翻转[1 , n]。这种极端情况，我们的程序会崩掉，所以先加两个哨兵。
完整代码！！！已经结束咧！！！#includeusing namespace std; const int N = 1e5, INF = 0x3f3f3f3f; int n, m, bval [N + 5]; struct Splay { int tot, root; int siz [N + 5]; int val [N + 5]; bool tag [N + 5]; int ch [N + 5] [2], fa [N + 5]; void Begin () { bval [1] = -INF; bval [n + 2] = INF; for (int i = 1; i <= n; ++i) bval [i + 1] = i; root = build (0, 1, n + 2); } int build (const int &y, const int &l, const int &r) { if (l > r) return 0; int x = ++tot; int mid = l + r >> 1; fa [x] = y; val [x] = bval [mid]; ch [x] [0] = build (x, l, mid - 1); ch [x] [1] = build (x, mid + 1, r); push_up (x); return x; } inline void rotate (const int &x) { int y = fa [x], z = fa [y]; bool d1 = cald (y), d2 = cald (x); push_down (y); push_down (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, 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 find (int k) { int x = root; while (x) { 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 (find (l)); splay (find (r), 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] != INF && val [x] != -INF) 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]); tag [ch [x] [0]] ^= 1; tag [ch [x] [1]] ^= 1; tag [x] = false; } } } T; int main () { scanf ("%d%d", &n, &m); T.Begin (); for (int i = 1, l, r; i <= m; ++i) { scanf ("%d%d", &l, &r); T.Reverse (l, r + 2); } T.Print (T.root); return 0; }
