【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

4 4
1 1 3 2
1 2 4 -1
2 1 3
3 2 4

Sample Output

2
【数据范围】
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
",splay_tree.query(l, r));//查询l到r的最大值 
199         }
200     }
201     return 0;
202 }