第一次接触splay。找了几道题写自己的模板。。每次写错东西都到处找错，splay的操作方式真的很多，虽然说思路简单。。但是真的很怕写错orz
传说中能解决各种区间翻转问题的乱搞树。就是splay，他的核心，就是splay。应该叫rotate，翻转吧。
学习旋转的时候参考了这篇博客：
http://www.cnblogs.com/yousiki/p/6147455.html
背景有点花。。f12把background去了。如果要看图的话，可以看那边，这里就不画图了。
旋转，通常有左旋和右旋。对于左旋来说，假设p为根节点，x为p的左儿子节点，现在要将x旋转到p那个位置。
那么，p会成为x的右儿子结点，那这个时候，x的右儿子结点的东西应该放到哪里去呢。
可以想象下，p原本的左儿子节点是x，但是现在p成了x的右儿子结点，他的左儿子节点就空了。
那么我们可以把x的右儿子结点接到p的左儿子节点上。那么这样就完成了一次左旋。至于为什么这样操作之后，这个树还是满足二叉平衡树呢，因为二叉平衡树满足，左儿子树的数一定比当前节点小，右儿子树的数一定比当前节点大。
那把p变成x的右儿子，原本p及p的右儿子就一定比x大，那旋转之后照样满足。
把x的右儿子节点变成p的左儿子节点，由于x的右儿子结点一定比x大，且比p小，操作之后，依然满足。
所以旋转是成立的。dalao们说，通常单旋是不够的，要双旋，单旋容易给退化成链。
那么当p为根时，我们进行一次左旋或者右旋就可以了，称为zig-step
如果当p不为根时，有两种情况。
一种是p和x同为左儿子，或者同为右儿子，那么我们只需要对p先做一次zig-step，再对x做一次zig-step即可。这种称之为zig-zig-step
如果p和x不为同方向的儿子，我们需要先对x进行一次zig-step到p，再进行反着得zig-step，也就叫zag-step到根。这种称之为zig-zag-step图的话就不画啦，字太丑orz。可以理论上去偷看下别人的旋转。
旋转操作完毕之后，就可以做各式各样的操作了。
例如，求区间和，求区间数，翻转区间，截断区间。
说了那么多，还是做一下经典题目。
传送门：http://acm.hdu.edu.cn/showproblem.php?pid=3487
题目大意：
有一个长度为n的序列：1…n
有两种操作
1、CUT，将 [a, b]下标的数切断，切断后找到第c个位置的数，放在他后面。
2、FLIP，将[a, b]区间翻转
思路：
对于截断，可以这么操作。
将a-1位置的数旋转到root
将b+1位置的数旋转到root的右儿子结点
那么，现在root的右儿子的左儿子节点的那棵子树就是我们要操作的区间。
先将root右儿子和区间树的关系去除。
再找出第c的位置。
将c旋转到root。
这个时候将区间树作为root的右儿子的左儿子，操作完成。对于翻转，可以这么操作。
同理截断
将a-1位置的数旋转到root
将b+1位置的数旋转到root的右儿子结点。
那么现在root的右儿子的左儿子节点的那棵子树就是我们要操作的区间。
我们给他们的root打上lazy标记，证明这个区间要翻转。
当进行rotate的时候，我们更新标记，像线段树那样，将要翻转的点的两个子树交换即可。
代码上都打满了注释。
/* @resources: @date: 2017-09-02 @author: QuanQqqqq @algorithm: splay */
#include <stdio.h>
#include <algorithm>
#include <string.h>#define ll long longusing namespace std;int n;struct SplayTree {const static int MAX_SIZE = 3e5 + 10;const static int INF = 0x7ffffff;int tree[MAX_SIZE][2], father[MAX_SIZE]; //该点的左右儿子，该点的爸爸节点， int size[MAX_SIZE]; //该点的子节点数 int val[MAX_SIZE]; //每个点的价值 int root, sz; //该树的根，该树的节点数int cnt; //中序遍历指针 int rev[MAX_SIZE]; //翻转区间，懒惰更新int node[MAX_SIZE]; //记录节点的下标void new_node(int &r, int fa, int v) {r = ++sz;father[r] = fa;val[r] = v;rev[r] = tree[r][0] = tree[r][1] = 0;}void modify(int x) {if (!x) {return ;}rev[x] ^= 1;}//更新节点数 void push_up(int r) {size[r] = size[tree[r][0]] + size[tree[r][1]] + 1;}//lazy更新 void push_down(int r) {if (r && rev[r]) {swap(tree[r][0], tree[r][1]); //翻转 modify(tree[r][0]);modify(tree[r][1]);modify(r);}}void build(int &rt, int l, int r, int fa) { //建一棵满的二叉平衡树 if (l > r) {return ;}int mid = l + r >> 1;new_node(rt, fa, mid);build(tree[rt][0], l, mid - 1, rt);build(tree[rt][1], mid + 1, r, rt);push_up(rt);}void clear() {sz = root = cnt = 0;size[root] = tree[0][0] = tree[0][1] = rev[0] = father[0] = 0;memset(rev, 0, sizeof(rev)); new_node(root, 0, -1);new_node(tree[root][1], root, -1);size[root] = 2;build(tree[tree[root][1]][0], 1, n, tree[root][1]); //建一棵在n+1左边的完全二叉平衡树 push_up(tree[root][1]);push_up(root);}void rotate(int x, int k) { //x是节点，k判断是左旋还是右旋 int y = father[x];push_down(y);push_down(x);tree[y][!k] = tree[x][k]; //先变两边的儿子 father[tree[x][k]] = y; //再将x的儿子的爸爸变成y if (father[y]) { //如果不是root，将y爸爸的儿子也变一下 tree[father[y]][tree[father[y]][1] == y] = x;}father[x] = father[y]; //更新x的父亲成y的父亲 father[y] = x; //更新y的父亲成x tree[x][k] = y; //更新x的儿子成y push_up(y);}void splay(int x, int r) { //将x旋转到r的儿子，这里注意是儿子！ if (r == 0) {root = x;}push_down(x);while (father[x] != r) {if (father[father[x]] == r) { //zig-step rotate(x, tree[father[x]][0] == x);return ;}int y = father[x];int k = tree[father[y]][0] == y; //判断上上层是否是左边 if (tree[y][k] == x) { // zig-zag-steprotate(x, !k);rotate(x, k);} else { // zig-zig-steprotate(y, k);rotate(x, k);}} push_up(x);} int insert(int v) { //插入值，插入完毕后进行splay操作，将插入的位置splay到root int r = root;while (tree[r][val[r] < v]) {if (val[r] == v) {splay(r, 0);return 0;}push_down(r);r = tree[r][val[r] < v];}new_node(tree[r][val[r] < v], r, v);splay(tree[r][val[r] < v], 0);return 1;}int get_kth(int r, int k) { //获得第k大的root push_down(r);int siz = size[tree[r][0]];if (siz == k - 1) {return r;}if (siz >= k) {return get_kth(tree[r][0], k);} else {return get_kth(tree[r][1], k - siz - 1);}}int get_min(int x) { //获得最小值的位置 push_down(x);while (tree[x][0]) {x = tree[x][0];push_down(x);}return x;}int get_max(int x) { //获得最大值的位置 push_down(x);while (tree[x][1]) {x = tree[x][1];push_down(x);}return x;}int get_next(int x) { //获得比x下标大一点的值 push_down(x);int rg = tree[x][1];push_down(rg);if (rg == 0) {return INF;}while (tree[rg][0]) {rg = tree[rg][0];push_down(rg);}return val[rg] - val[x]; //这里返回时可以更改 } int get_pre(int x) { //获得比x下标小一点的值 push_down(x);int lt = tree[x][0];push_down(lt);if (lt == 0) {return INF;}while (tree[lt][1]) {lt = tree[lt][1];push_down(lt);}return val[x] - val[lt];}void cut(int a, int b, int c) { //将[a,b]切断，放在切断后第c个数后面int x = get_kth(root, a); //这里由于树是[0,n+1]的，所以要找的区间如果是[a,b]则需要将 a-1旋转到根，b+1旋转到a-1的子根，那么b+1的左子树就是要的区间 int y = get_kth(root, b + 2); //又由于从0开始，所以都+1splay(x, 0);splay(y, root);int p = tree[tree[root][1]][0]; //区间树的根 tree[tree[root][1]][0] = 0; //切断 push_up(tree[root][1]);push_up(root); //更新一下节点数int z = get_kth(root, c + 1); //切断后就可以找第c位数splay(z, 0); //旋转到根int m = get_min(tree[root][1]); //找一下右子树最小的位置splay(m, root); //旋转到根的右儿子，那么这个最小的位置的左儿子就是空的了tree[tree[root][1]][0] = p; //放回去 father[tree[tree[root][1]][0]] = tree[root][1];push_up(tree[root][1]); //更新节点 push_up(root);} void reversal(int a, int b) { //[a, b]内区间交换 int x = get_kth(root, a);int y = get_kth(root, b + 2);splay(x, 0); //左区间旋转到根 splay(y, root); //右区间旋转到根的左边，那么根的右儿子结点的左儿子节点为所需区间rev[tree[tree[root][1]][0]] ^= 1; }void in_order(int r) { //中序遍历 if (r == 0) {return ;}push_down(r);in_order(tree[r][0]);if (cnt <= n && cnt >= 1) {if (cnt > 1) {printf(" ");}printf("%d", val[r]);}cnt++;in_order(tree[r][1]);}
};SplayTree spl;int main() {int m, a, b, c;char ch[10];while (~scanf("%d %d", &n, &m) && ~n && ~m) {spl.clear();getchar();while (m--) {scanf("%s", ch);if (ch[0] == 'C') {scanf("%d %d %d", &a, &b, &c);spl.cut(a, b, c);} else {scanf("%d %d", &a, &b);spl.reversal(a, b);}}spl.in_order(spl.root);puts("");}
}楼下日常更新自己的模板
struct SplayTree {const static int MAX_SIZE = 3e5 + 10;const static int INF = 0x7ffffff;int tree[MAX_SIZE][2], father[MAX_SIZE]; //该点的左右儿子，该点的爸爸节点，int size[MAX_SIZE]; //该点的子节点数int val[MAX_SIZE]; //每个点的价值int root, sz; //该树的根，该树的节点数int cnt; //中序遍历指针int rev[MAX_SIZE]; //翻转区间，懒惰更新int sum[MAX_SIZE]; //求子树的和int lazy[MAX_SIZE]; //求和，懒惰更新void Treaval(int x) {if (x) {Treaval(tree[x][0]);printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d size = %2d ,key = %2d ,sum = %2d\n", x, tree[x][0], tree[x][1], father[x], size[x], val[x], sum[x]);Treaval(tree[x][1]);}}void debug() {printf("%d\n",root);Treaval(root);}void modify(int x) {if (!x) {return ;}rev[x] ^= 1;}//更新节点数void push_up(int r) {size[r] = size[tree[r][0]] + size[tree[r][1]] + 1;sum[r] = sum[tree[r][0]] + sum[tree[r][1]] + val[r];}//lazy更新void push_down(int r) {if (r && rev[r]) { //翻转swap(tree[r][0], tree[r][1]);modify(tree[r][0]);modify(tree[r][1]);modify(r);}if (r && lazy[r]) { //更新和sum[tree[r][0]] += lazy[r];sum[tree[r][1]] += lazy[r];lazy[tree[r][0]] += lazy[r];lazy[tree[r][1]] += lazy[r];lazy[r] = 0;}}void new_node(int &r, int fa, int v) {r = ++sz;father[r] = fa;sum[r] = val[r] = v;rev[r] = tree[r][0] = tree[r][1] = 0;}void build(int &rt, int l, int r, int fa) { //建一棵满的二叉平衡树if (l > r) {return ;}int mid = l + r >> 1;new_node(rt, fa, mid);build(tree[rt][0], l, mid - 1, rt);build(tree[rt][1], mid + 1, r, rt);push_up(rt);}void clear() {sz = root = cnt = 0;size[root] = tree[0][0] = tree[0][1] = rev[0] = father[0] = sum[0] = lazy[0] = 0;memset(rev, 0, sizeof(rev));new_node(root, 0, 0);new_node(tree[root][1], root, 0);size[root] = 1;
// build(tree[tree[root][1]][0], 1, n, tree[root][1]); //建一棵在n+1左边的完全二叉平衡树push_up(tree[root][1]);push_up(root);}void rotate(int x, int k) { //x是节点，k判断是左旋还是右旋int y = father[x];push_down(y);push_down(x);tree[y][!k] = tree[x][k]; //先变两边的儿子father[tree[x][k]] = y; //再将x的儿子的爸爸变成yif (father[y]) { //如果不是root，将y爸爸的儿子也变一下tree[father[y]][tree[father[y]][1] == y] = x;}father[x] = father[y]; //更新x的父亲成y的父亲father[y] = x; //更新y的父亲成xtree[x][k] = y; //更新x的儿子成ypush_up(y);}void splay(int x, int r) { //将x旋转到r的儿子，这里注意是儿子！if (r == 0) {root = x;}push_down(x);while (father[x] != r) {if (father[father[x]] == r) { //zig-steprotate(x, tree[father[x]][0] == x);return ;}int y = father[x];int k = tree[father[y]][0] == y; //判断上上层是否是左边if (tree[y][k] == x) { // zig-zag-steprotate(x, !k);rotate(x, k);} else { // zig-zig-steprotate(y, k);rotate(x, k);}}push_up(x);}int insert(int v) { //插入值，插入完毕后进行splay操作，将插入的位置splay到rootint r = root;while (tree[r][val[r] < v]) {if (val[r] == v) {splay(r, 0);return 0;}push_down(r);r = tree[r][val[r] < v];}new_node(tree[r][val[r] < v], r, v);splay(tree[r][val[r] < v], 0);return 1;}int get_kth(int r, int k) { //获得第k大的rootpush_down(r);int siz = size[tree[r][0]];if (siz == k - 1) {return r;}if (siz >= k) {return get_kth(tree[r][0], k);} else {return get_kth(tree[r][1], k - siz - 1);}}int get_min(int x) { //获得最小值的位置push_down(x);while (tree[x][0]) {x = tree[x][0];push_down(x);}return x;}int get_max(int x) { //获得最大值的位置push_down(x);while (tree[x][1]) {x = tree[x][1];push_down(x);}return x;}int get_next(int x) { //获得比x下标大一点的值push_down(x);int rg = tree[x][1];push_down(rg);if (rg == 0) {return INF;}while (tree[rg][0]) {rg = tree[rg][0];push_down(rg);}return val[rg] - val[x]; //这里返回时可以更改}int get_pre(int x) { //获得比x下标小一点的值push_down(x);int lt = tree[x][0];push_down(lt);if (lt == 0) {return INF;}while (tree[lt][1]) {lt = tree[lt][1];push_down(lt);}return val[x] - val[lt];}void cut(int a, int b, int c) { //将[a,b]切断，放在切断后第c个数后面int x = get_kth(root, a); //这里由于树是[0,n+1]的，所以要找的区间如果是[a,b]则需要将 a-1旋转到根，b+1旋转到a-1的子根，那么b+1的左子树就是要的区间int y = get_kth(root, b + 2); //又由于从0开始，所以都+1splay(x, 0);splay(y, root);int p = tree[tree[root][1]][0]; //区间树的根tree[tree[root][1]][0] = 0; //切断push_up(tree[root][1]);push_up(root); //更新一下节点数int z = get_kth(root, c + 1); //切断后就可以找第c位数splay(z, 0); //旋转到根int m = get_min(tree[root][1]); //找一下右子树最小的位置splay(m, root); //旋转到根的右儿子，那么这个最小的位置的左儿子就是空的了tree[tree[root][1]][0] = p; //放回去father[tree[tree[root][1]][0]] = tree[root][1];push_up(tree[root][1]); //更新节点push_up(root);}void reversal(int a, int b) { //[a, b]内区间交换int x = get_kth(root, a);int y = get_kth(root, b + 2);splay(x, 0); //左区间旋转到根splay(y, root); //右区间旋转到根的左边，那么根的右儿子结点的左儿子节点为所需区间rev[tree[tree[root][1]][0]] ^= 1;}void in_order(int r) { //中序遍历if (r == 0) {return ;}push_down(r);in_order(tree[r][0]);if (cnt >= 1) {printf(" ");}printf("%d", val[r]);cnt++;in_order(tree[r][1]);}int query_sum(int a, int b) {int x = get_kth(root, a);int y = get_kth(root, b + 2);splay(x, 0);splay(y, root);push_up(y);push_up(x);return sum[tree[y][0]];}void add_sum(int a, int v) {int x = get_kth(root, a + 1);splay(x, 0);val[x] += v;push_up(x);}void del() { //这里删除被旋转到root的那个 if (!tree[root][0] || !tree[root][1]) { //如果发现左子树或者右子树是空，直接删除root = tree[root][0] + tree[root][1];father[root] = 0;return ;}int k = get_min(tree[root][1]); //找到最小的那个splay(k, root);tree[tree[root][1]][0] = tree[root][0];root = tree[root][1];father[tree[root][0]] = root;father[root] = 0;push_up(root);}//这个插入跟之前那个插入不同void insert(int &r, int k, int fa) { //这里插入到最前的那个位置 if (r == 0) {new_node(r, fa, k);return ;}insert(tree[r][0], k, r);push_up(r);}//将某个元素放到最顶部void top_point(int a) {int y = node[a];splay(y, 0);del();insert(root, a, 0);splay(sz, 0); //听说这步不加会TLE}
};