// 此博文为迁移而来，写于2015年7月18日，不代表本人现在的观点与看法。原始地址：http://blog.sina.com.cn/s/blog_6022c4720102w6rg.html
UPDATE（20180831）：重写代码，微调。
一、前言
这玩意儿真的搞了我好久，当然前一阵子一直都没有去管它，最近直接参照了YML（@YMDragon）的程序，感觉还是不错的，大概看得懂了，就是逻辑关系有点扯。好，废话不多说……
二、概念
平衡树的全称为：平衡二叉搜索树，功能很强大，带来的后果就是代码非常复杂。首先大家应该都知道二叉搜索树是什么了，那么前面加一个平衡的含义在于什么？根据读入顺序 { 80,30,90,20,40,35,38 }，我们先构造出一棵二叉搜索树，如图：
显然，这棵树长得有点畸形，其根节点左儿子部分节点明显过多。然而这不仅仅是看起来不舒服的问题，但我们要在树上进行某项询问或是某项操作的时候，如果深度过大，将会明显影响到时间效率，可以举一个极端的例子——如果我们构造出的是一条链，那么时间复杂度可想而知。而平衡的含义就出现了，让这棵树长得更像一棵树！在操作的时候能够提高效率。写平衡树的方式有很多种，如：Splay，Treap，红黑树和AVL树等等。Splay相比之下功能强大，代码量较大，今天的重点就在Splay。
三、伸展
Splay的中文是伸展，故Splay又名伸展树。Splay主要存在三种操作，下面一一介绍：
1、Zig操作：目标节点X是根节点的左（右）儿子，则将目标节点右（左）旋转至根节点。
2、Zig-zig操作：目标节点X不是根节点的子节点，且为其父节点的左（右）儿子，其父节点为其爷爷节点的左（右）儿子，则将目标节点X和其父节点先后进行右（左）旋。
3、Zig-zag操作：目标节点X不是根节点的子节点，且为其父节点的左（右）儿子，其父节点为其爷爷节点的右（左）儿子，则将目标节点X进行右（左）旋，其父节点进行左（右）旋。
具体操作的话，旋转多为自下而上的递归旋转，直到把目标节点旋转至根节点。
四、应用
平衡树存在一个共同作用也就是前文所提——平衡（废话呢）。但是今天的主题是Splay，之前也说过了它功能强大，那么强大在哪里？第一眼看题目你也许根本想不到要用Splay。现在我们来看一道神题：
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 #define MAXN 500005 8 #define INF 0x3f3f3f3f 9 10 int n, m, p, tot, l, r, a[MAXN], rt, x; 11 char ch[10]; 12 queue Q; 13 14 struct tree { 15 int x, sum, l, r, m, s[2], f, w, ta, tb; 16 } t[MAXN]; 17 18 void mksame(int o, int w) { 19 if (!o) return; 20 t[o].w = w, t[o].ta = 1, t[o].sum = t[o].w * t[o].x; 21 t[o].l = t[o].r = t[o].m = t[o].w > 0 ? t[o].sum : t[o].w; 22 } 23 24 void rev(int o) { 25 if (!o) return; 26 swap(t[o].s[0], t[o].s[1]), t[o].tb ^= 1; 27 swap(t[o].l, t[o].r); 28 } 29 30 void push(int o) { 31 if (!o) return; 32 if (t[o].ta) mksame(t[o].s[0], t[o].w), mksame(t[o].s[1], t[o].w), t[o].ta = 0; 33 if (t[o].tb) rev(t[o].s[0]), rev(t[o].s[1]), t[o].tb = 0; 34 } 35 36 void upd(int o) { 37 if (!o) return; 38 push(o); 39 int ls = t[o].s[0], rs = t[o].s[1]; 40 t[o].x = t[ls].x + t[rs].x + 1; 41 t[o].sum = t[ls].sum + t[rs].sum + t[o].w; 42 t[o].l = max(t[ls].l, t[ls].sum + t[o].w + max(t[rs].l, 0)); 43 t[o].r = max(t[rs].r, t[rs].sum + t[o].w + max(t[ls].r, 0)); 44 t[o].m = max(max(t[ls].m, t[rs].m), t[o].w + max(t[ls].r, 0) + max(t[rs].l, 0)); 45 } 46 47 void rot(int o) { 48 int f = t[o].f, g = t[f].f, x = (t[f].s[1] == o), s = t[o].s[x ^ 1]; 49 if (g) t[o].f = g, t[g].s[t[g].s[1] == f] = o; 50 else t[o].f = 0, rt = o; 51 t[f].s[x] = s; 52 if (s) t[s].f = f; 53 t[f].f = o, t[o].s[x ^ 1] = f; 54 upd(f), upd(o); 55 } 56 57 void splay(int o) { 58 int tot = 0; 59 for (int x = o; x; x = t[x].f) tot++, a[tot] = x; 60 for (int i = tot; i >= 1; i--) push(a[i]); 61 while (t[o].f) rot(o); 62 } 63 64 void build(int o, int l, int r) { 65 int m = (l + r) >> 1; 66 if (l < m) t[o].s[0] = Q.front(), Q.pop(), build(t[o].s[0], l, m - 1), t[t[o].s[0]].f = o; 67 scanf("%d", &t[o].w); 68 if (m < r) t[o].s[1] = Q.front(), Q.pop(), build(t[o].s[1], m + 1, r), t[t[o].s[1]].f = o; 69 upd(o); 70 } 71 72 void ins() { 73 int rt = Q.front(); 74 Q.pop(), build(rt, 1, tot); 75 if (l) t[l].s[1] = rt, t[rt].f = l; 76 else t[r].s[0] = rt, t[rt].f = r; 77 upd(l), upd(r); 78 } 79 80 void dfs(int o) { 81 if (t[o].s[0]) dfs(t[o].s[0]); 82 if (t[o].s[1]) dfs(t[o].s[1]); 83 Q.push(o), memset(t + o, 0, sizeof(t[o])); 84 } 85 86 void del() { 87 if (l) dfs(t[l].s[1]), t[l].s[1] = 0; 88 else dfs(t[r].s[0]), t[r].s[0] = 0; 89 } 90 91 void init() { 92 freopen("splay.in", "r", stdin); 93 freopen("splay.out", "w", stdout); 94 scanf("%d %d", &n, &m); 95 for (int i = 1; i <= MAXN; i++) Q.push(i); 96 t[0].l = t[0].r = t[0].m = -INF; 97 rt = Q.front(), Q.pop(), build(rt, 1, n); 98 } 99 100 int rk(int o) {101 int x = rt;102 while (x) {103 push(x);104 if (t[t[x].s[0]].x + 1 == o) return x;105 if (t[t[x].s[0]].x >= o) x = t[x].s[0];106 else o -= t[t[x].s[0]].x + 1, x = t[x].s[1];107 }108 return 0;109 }110 111 int main() {112 init();113 for (int i = 1; i <= m; i++) {114 scanf("%s", ch);115 if (ch[2] != 'X') scanf("%d %d", &p, &tot);116 if (ch[0] == 'I') splay(l = rk(p)), splay(r = rk(p + 1)), ins();117 else if (ch[2] != 'X') splay(l = rk(p - 1)), splay(r = rk(p + tot));118 if (ch[0] == 'D') del();119 if (ch[2] == 'K') scanf("%d", &x), mksame(l ? t[l].s[1] : t[r].s[0], x);120 if (ch[0] == 'R') rev(l ? t[l].s[1] : r ? t[r].s[0] : rt);121 if (ch[0] == 'G') printf("%d\n", l ? t[t[l].s[1]].sum : t[t[r].s[0]].sum);122 else if (ch[2] == 'X') printf("%d\n", t[rt].m);123 else if (ch[0] != 'I') upd(l), upd(r);124 }125 return 0;126 }