【bzoj1251】序列终结者（伸展树）
Description
网上有许多题，就是给定一个序列，要你支持几种操作：A、B、C、D。一看另一道题，又是一个序列 要支持几种操作：D、C、B、A。尤其是我们这里的某人，出模拟试题，居然还出了一道这样的，真是没技术含量……这样 我也出一道题，我出这一道的目的是为了让大家以后做这种题目有一个“库”可以依靠，没有什么其他的意思。这道题目 就叫序列终结者吧。 【问题描述】 给定一个长度为N的序列，每个序列的元素是一个整数（废话）。要支持以下三种操作： 1. 将[L,R]这个区间内的所有数加上V。 2. 将[L,R]这个区间翻转，比如1 2 3 4变成4 3 2 1。 3. 求[L,R]这个区间中的最大值。 最开始所有元素都是0。
Input
第一行两个整数N，M。M为操作个数。 以下M行，每行最多四个整数，依次为K，L，R，V。K表示是第几种操作，如果不是第1种操作则K后面只有两个数。
Output
对于每个第3种操作，给出正确的回答。
Sample Input
1 1 3 2
1 2 4 -1
2 1 3
3 2 4
Sample Output
【数据范围】
N<=50000，M<=100000。
样例说明：
| 0 | 0 | 0 | 0 | |
| 1 1 3 2 | 2 | 2 | 2 | 0 |
| 1 2 4 -1 | 2 | 1 | 1 | -1 |
| 2 1 3 | 1 | 1 | 2 | -1 |
| 3 2 4 | 2 | |||
分析：
暴力的话，操作1增加操作，操作2翻转操作，操作3查询操作的复杂度都是O(n)，并且有m个查询的话，O(mn)肯定得爆炸。
关键点：
1. 伸展树为左小右大的二叉树，所以旋转操作不会影响树的性质
2. 区间操作为：
int u = select(L - 1), v = select(R + 1);
splay(u, 0); splay(v, u); //通过旋转操作把询问的区间聚集到根的右子树的左子树下
因为伸展树为左小右大的二叉树，旋转操作后的所以对于闭区间[L, R]之间的所有元素都聚集在根的右子树的左子树下
因为闭区间[L, R]，
1) 所以每次都要查开区间(L - 1, R + 1)，
2) 所以伸展树元素1对应的标号为2，
3) 所以node[0]对应空节点，node[1]对应比所以元素标号都小的点，node[2 ~ n + 1]对应元素1 ~ n，node[n + 2]对应比所有元素标号都打的点，其中node[0], node[1], node[n + 2]都是虚节点，不代表任何元素。
每次进行序列操作时，把l-1旋转到根，把r+1旋转到根的右儿子，r+1的左子树就是整个区间[l,r]。
我们可以用Splay的每个节点记录该节点对应子树的信息，那么每次询问只要输出r+1的左子树中的最大值，即代码中的mx[t[y][0]]。
为了避免Splay中有节点0，我们将所有节点的编号加1。又因为要旋转l-1和r+1，所以在Splay插入节点为1到n+2。(原因显然…大家自己脑补)
这道题用Splay的提根操作达到了区间操作的目的，方法很巧妙。
另外我觉得这道题有几点需要注意：
①要理解Splay中节点的含义以及节点所记录的信息。
②区间的翻转操作很巧妙，只需要将标记下传并且交换左右子树，并不需要修改节点的max和size。
③每次find操作都要pushdown，这样就可以保证节点x到根的路径上所有点都被更新，便于之后的旋转操作
总结
a. 这里区间加，所以无怪乎有延迟标记的思想，那就自然有了pushdown操作
b. 这里通过提根操作找到我们要操作的区间，
c. 区间加操作用的是延迟标记的思想
b. 区间最大值操作在排序二叉树中很简单（因为这个区间已经被我们旋转成一个区间了）
d. 区间翻转操作：这里用的是延迟标记的思想（区间加也是延迟标记），所以有rev做延迟标记，交换的话直接交换左右即可
e. 这里有翻转操作，这颗伸展树不一定是一颗二叉排序树，所以求最大值的话就像线段树那么求好了，每个节点多加个maxx标记即可
1 /*bzoj 1251 序列终结者 2 题意： 3 给定一个长度为N的序列，每个序列的元素是一个整数。要支持以下三种操作： 4 1. 将[L,R]这个区间内的所有数加上V; 5 2. 将[L,R]这个区间翻转，比如1 2 3 4变成4 3 2 1; 6 3. 求[L,R]这个区间中的最大值; 7 最开始所有元素都是0。 8 限制： 9 N <= 50000, M <= 100000 10 思路： 11 伸展树 12 13 关键点： 14 1. 伸展树为左小右大的二叉树，所以旋转操作不会影响树的性质 15 2. 区间操作为： 16 int u = select(L - 1), v = select(R + 1); 17 splay(u, 0); splay(v, u); //通过旋转操作把询问的区间聚集到根的右子树的左子树下 18 因为伸展树为左小右大的二叉树，旋转操作后的所以对于闭区间[L, R]之间的所有元素都聚集在根的右子树的左子树下 19 因为闭区间[L, R]， 20 1) 所以每次都要查开区间(L - 1, R + 1)， 21 2) 所以伸展树元素1对应的标号为2， 22 3) 所以node[0]对应空节点，node[1]对应比所以元素标号都小的点，node[2 ~ n + 1]对应元素1 ~ n，node[n + 2]对应比所有元素标号都打的点，其中node[0], node[1], node[n + 2]都是虚节点，不代表任何元素。 23 */ 24 #include <iostream> 25 #include <cstdio> 26 using namespace std; 27 //左右孩子简便写 28 #define LS(n) node[(n)].ch[0] 29 #define RS(n) node[(n)].ch[1] 30 31 const int N = 1e5 + 5; 32 const int INF = 0x3f3f3f3f; 33 struct Splay { 34 struct Node{ 35 int fa, ch[2];//节点的父亲以及两个孩子 36 bool rev;//翻转标记 37 int val, add, maxx, size;//值，增加的延迟标记，最大值，子树的大小 38 void init(int _val) { 39 val = maxx = _val;//初始化最大值和值 40 size = 1;//子树大小 41 add = rev = ch[0] = ch[1] = 0;//初始化左右子树和延迟标记和反转标记 42 } 43 } node[N];//n个节点 44 int root;//树根 45 46 void up(int n) {//右节点向父亲更新 47 //这是求子树的最大值，树的最大值就是取树根，左子树，右子树三者中的最大值 48 node[n].maxx = max(node[n].val, max(node[LS(n)].maxx, node[RS(n)].maxx)); 49 //这是更新树根的大小，左子树+右子树+根 50 node[n].size = node[LS(n)].size + node[RS(n)].size + 1; 51 } 52 53 void down(int n) {//区间增加的延迟标记往下传的操作 54 if(n == 0) return ;//空节点 55 if(node[n].add) {//如果增加的延迟标记不为0 56 if(LS(n)) {//如果分别有左右子树，就更新左右子树 57 //标准的线段树区间操作的例子 58 node[LS(n)].val += node[n].add; 59 node[LS(n)].maxx += node[n].add; 60 node[LS(n)].add += node[n].add; 61 } 62 if(RS(n)) { 63 node[RS(n)].val += node[n].add; 64 node[RS(n)].maxx += node[n].add; 65 node[RS(n)].add += node[n].add; 66 } 67 node[n].add = 0;//增加延迟标记传下去了，自己的当然要赋值为0 68 } 69 if(node[n].rev) {//这是区间翻转的延迟标记 70 if(LS(n)) node[LS(n)].rev ^= 1;//翻转延迟标记往下传 71 if(RS(n)) node[RS(n)].rev ^= 1; 72 swap(LS(n), RS(n));//交换左右子树 73 node[n].rev = 0;//翻转延迟标记设置为0 74 } 75 } 76 77 //左旋和右旋的合集 ，将节点n按照kind方式旋转 78 void rotate(int n, bool kind) { 79 int fn = node[n].fa; 80 int ffn = node[fn].fa; 81 node[fn].ch[!kind] = node[n].ch[kind]; 82 node[node[n].ch[kind]].fa = fn; 83 84 node[n].ch[kind] = fn; 85 node[fn].fa = n; 86 87 node[ffn].ch[RS(ffn) == fn] = n; 88 node[n].fa = ffn; 89 up(fn); 90 } 91 92 //将节点n伸展到goal的 位置去 93 void splay(int n, int goal) { 94 while(node[n].fa != goal) { 95 int fn = node[n].fa; 96 int ffn = node[fn].fa; 97 down(ffn); down(fn); down(n); 98 bool rotate_n = (LS(fn) == n); 99 bool rotate_fn = (LS(ffn) == fn); 100 if(ffn == goal) rotate(n, rotate_n); 101 else { 102 if(rotate_n == rotate_fn) rotate(fn, rotate_fn); 103 else rotate(n, rotate_n); 104 rotate(n, rotate_fn); 105 } 106 } 107 up(n); 108 if(goal == 0) root = n; 109 } 110 111 //在树种找位置为pos的点，其实和二叉查找树里面找排名为pos的点的方式一样 112 int select(int pos) { 113 int u = root; 114 down(u);//区间加和区级翻转延迟标记下传 115 while(node[LS(u)].size != pos) {//左孩子的大小不等于pos 116 if(pos < node[LS(u)].size)//如果pos在左孩子就往左孩子走 117 u = LS(u);// 118 else {//pos在右孩子 119 pos -= node[LS(u)].size + 1;//pos减去左孩子和根的大小 120 u = RS(u);//往右孩子走 121 } 122 down(u);//延迟标记下传 123 } 124 return u; 125 } 126 127 //查找l到r这个区间 128 int query(int L, int R) { 129 //u节点就是找到的l-1的节点，v节点就是找到的r+1的节点 130 int u = select(L - 1), v = select(R + 1); 131 //将u节点旋转到0的位置（根），将v节点旋转到u的位置，那么 132 splay(u, 0); splay(v, u); //通过旋转操作把询问的区间聚集到根的右子树的左子树下 133 return node[LS(v)].maxx; 134 } 135 136 //区间加操作 137 void update(int L, int R, int val) { 138 //把区间调上来 139 int u = select(L - 1), v = select(R + 1); 140 splay(u, 0); splay(v, u); 141 //标准的区间加操作 142 node[LS(v)].val += val; 143 node[LS(v)].maxx += val; 144 node[LS(v)].add += val;//延迟标记下传 145 } 146 147 //区间翻转操作 148 void reverse(int L, int R) { 149 //找区间 150 int u = select(L - 1), v = select(R + 1); 151 splay(u, 0); splay(v, u); 152 //翻转延迟标记置为1 153 node[LS(v)].rev ^= 1; 154 } 155 156 int build(int L, int R) { 157 if(L > R) return 0; 158 if(L == R) return L; 159 int mid = (L + R) >> 1; 160 int r_L, r_R; 161 LS(mid) = r_L = build(L, mid - 1); 162 RS(mid) = r_R = build(mid + 1, R); 163 node[r_L].fa = node[r_R].fa = mid; 164 up(mid); 165 return mid; 166 } 167 168 void init(int n) { 169 node[0].init(-INF); node[0].size = 0; 170 node[1].init(-INF); 171 node[n + 2].init(-INF); 172 for(int i = 2; i <= n + 1; ++i) 173 node[i].init(0); 174 175 root = build(1, n + 2); 176 node[root].fa = 0; 177 178 node[0].fa = 0; 179 LS(0) = root; 180 } 181 } splay_tree; 182 183 int main() { 184 int n, m; 185 scanf("%d%d", &n, &m); 186 splay_tree.init(n);//初始化 187 for(int i = 0; i < m; ++i) { 188 int op, l, r, v; 189 scanf("%d", &op); 190 if(op == 1) {//操作1，区间加 191 scanf("%d%d%d", &l, &r, &v); 192 splay_tree.update(l, r, v);//l到r区间上面加上v 193 } else if(op == 2) {//操作2，区间翻转 194 scanf("%d%d", &l, &r); 195 splay_tree.reverse(l, r);//翻转l到r区间 196 } else { 197 scanf("%d%d", &l, &r); 198 printf("%d\n",splay_tree.query(l, r));//查询l到r的最大值 199 } 200 } 201 return 0; 202 }
