Andrewei's Blog
0%

伸展树(SplayTree)

发表于 更新于 分类于 ，

预备知识

  1. 树的遍历
  2. 二叉树的基本知识
  3. 排序二叉树的基本知识
  4. 线段树区间更新和区间查询知识
  5. 平衡排序二叉树的基本知识(非必须)

简介

伸展树(SplayTree) 是一种经过改进的平衡排序二叉树, 他跟平衡二叉树的操作非常类似，同时也有很多不同。

伸展树的性质有:

  • 通过节点的旋转来调整树的结构来达到某种目的;
  • 整棵树保证有序性，即无论怎么旋转整棵树的中序遍历的顺序是一定的，不会发生改变;
  • 伸展树不能保证树是“平衡”的，也导致了它不能保证所有操作的时间复杂度都在 $O(log(n))$, 但是从统计意义上来讲，它可以使得所有操作的均摊复杂度为 $(O(log(n))$;
  • 伸展树保证了“八二原则”（或者称为“九一原则”，即 $80%$ 的操作都集中在 $20%$ 的数据上), 也就是说在伸展树中对某些值操作的次数越多，那么对这些数操作的复杂度就会越来越低，这个特性拥有非常好的现实意义。

基本操作

以下所有操作的示例代码以 区间更新，区间求和 问题为例给出，代码参考了kuangbin博客，特此说明.

** 代码说明: **

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#define key_value tree[tree[root].ch[1]].ch[0]
// 定义了一个宏，代表根节点的右儿子的左儿子，我们在进行操作时都会尽量把数据集中在这个地方
const int maxn = 100010;                    // 数据规模
const int INF = (1 << 29);                  // 定义了一个极值
struct Node{
    int ch[2];                              // 左右儿子
    int pre, val, size;                     // 父节点，当前节点的值，当前节点为根的子树的大小
    long long sum;                          // 当前节点为根的子树的和

    int rev, add, same;                     // 反转标记, 增量延迟标记， 区间所有元素相同标记
    int lx, rx, mx;                         // 从区间最左端开始的子序列最大和，从区间最右端开始的区间子序列最大和，整个区间里面子序列最大和
};

int root, total;                            // 根节点，节点数量
stack <int> mPool;                          // 内存池，用来存储删除节点时释放的节点, 以便之后使用
Node tree[maxn];                            // 树的所有节点

int n, q;                                   // n 个数， q 个询问
int data[maxn];                             // 原始数据

void updateAdd(int rt, int add);            // 更新增量延迟标记
void updateRev(int rt);                     // 更新反转延迟标记
void updateSame(int rt, int val);           // 更新区间数值相同延迟标记

void pushUp(int rt);                        // 回朔时根据子节点来更新父节点
void pushDown(int rt);                      // 向树的深处遍历时将父节点的延迟标记推到子节点

void newNode(int &rt, int pre, int val);    // 添加新节点, (当前根节点，父节点，添加的值)
void buildTree(int &cur, int l, int r, int pre, int *a);
                                            // 建树, (当前根节点，区间左端点，区间右端点，父节点，原始数据)
void init(int *data);                       // 初始化整棵树调用建树函数，(原始数据)

void rotate(int cur, int com);              // 单旋操作，将 cur 节点左(com==0)右(com==1)旋, (旋转的节点，控制左右旋)
void splay(int rt, int tar);                // 实现树的调整，将 rt 节点调整到 tar 节点的下面，(要调整的节点，目的节点)

int getKth(int rt, int k);                  // 得到第 k 个数，（当前根，第k个数）
int getValMinPos(int rt, int val);          // 得到比 val 大的最小值的位置(当前节点，val);
int getValPos(int rt, int val);             // 得到 val 的位置，（当前节点，val);
int getValRank(int rt, int val);            // 得到 val 的排名, （当前节点，val);
int getMin(int rt);                         // 得到最小的数字<树中的数基于大小排列>(当前节点);
int getMax(int rt);                         // 得到最大的数字<树中的数基于大小排列>(当前节点);
void insertOne(int x, int val);             // 在第 x 个数后面插入 val;
void erase(int rt);                         // 内存回收，在删除节点的时候调用(删除的节点);
void deleteOne(int k);                      // 回收第 k 个数
void insert(int pos, int cnt, int *val);    // 在第 pos 个数后插入 cnt 个数，这些数存放在 val 数组中
void Delete(int pos, int cnt);              // 从第 pos 个数开始连续删除 cnt 个数
void getSum(int l, int r);                  // 获取区间[l, r]中的和
void makeAdd(int l, int r, int val);        // 将 [l, r] 区间的所有值都增加 val
void makeSame(int pos, int cnt, int val);   // 从 pos 开始连续的 cnt 个数都变为 val
void revolve(int l, int r, int T);          // 区间滑动，将 [l, r] 区间循环右移 T 个单位
void reverse(int l, int r);                 // 区间反转，将 [l, r] 区间内的数完全反转
void getMaxSum(int pos, int cnt);           // 求从 pos 开始的连续 cnt 长度的区间内的子序列最大和

** 接下来边讲算法原理边实现代码: **

下面是 pushUp, pushDown 还有延迟标记的处理， 与线段树区间操作类似，不再赘述。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// 更新增量延迟标记
void updateAdd(int rt, int add){
    if(!rt) return;
    tree[rt].add += add;
    tree[rt].val += add;
    tree[rt].sum += (long long)add * tree[rt].size;
}

// 更新反转延迟标记
void updateRev(int rt){
    if(!rt) return;
    tree[rt].rev ^= 1;
    swap(tree[rt].lx, tree[rt].rx);
    swap(tree[rt].ch[0], tree[rt].ch[1]);
}

// 更新区间元素值相同延迟标记
void updateSame(int rt, int val){
    if(!rt) return;
    tree[rt].val = val;
    tree[rt].sum = val * tree[rt].size;
    tree[rt].lx = tree[rt].rx = tree[rt].mx = max(val, val * tree[rt].size);
    tree[rt].same = 1;
}

// 通过孩子节点的数据来更新父节点的数据
void pushUp(int rt){
    int lson = tree[rt].ch[0], rson = tree[rt].ch[1];

    // 更新节点的大小
    tree[rt].size = tree[lson].size + tree[rson].size + 1;

    // 更新该节点及其子树所有值的和
    tree[rt].sum = tree[lson].sum + tree[rson].sum + tree[rt].val;

    // 更新子序列最大值
    tree[rt].lx = max((long long)tree[lson].lx, tree[lson].sum + tree[rt].val + max(0, tree[rson].lx));
    tree[rt].rx = max((long long)tree[rson].rx, tree[rson].sum + tree[rt].val + max(0, tree[lson].rx));
    tree[rt].mx = max(0, tree[lson].rx) + tree[rt].val + max(0, tree[rson].lx);
    tree[rt].mx = max(tree[rt].mx, max(tree[lson].mx, tree[rson].mx));
}

// 将父节点的延迟标记更新到孩子节点
void pushDown(int rt){

    // 更新增量延迟标记
    if(tree[rt].add){
        updateAdd(tree[rt].ch[0], tree[rt].add);
        updateAdd(tree[rt].ch[1], tree[rt].add);
        tree[rt].add = 0;
    }

    // 更新区间相同标记
    if(tree[rt].same){
        updateSame(tree[rt].ch[0], tree[rt].val);
        updateSame(tree[rt].ch[1], tree[rt].val);
        tree[rt].same = 0;
    }

    // 更新反转标记
    if(tree[rt].rev){
        updateRev(tree[rt].ch[0]);
        updateRev(tree[rt].ch[1]);
        tree[rt].rev = 0;
    }
}

建树

建树时要考虑数据的顺序问题，这是由你需要求解的问题所决定的。这些顺序包括，按照插入数据的大小排序，数据的原始排列顺序等等。

参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
void newNode(int &rt, int pre, int val){
    if(!mPool.empty()){
        rt = mPool.top();
        mPool.pop();
    }else{
        rt = ++total;
    }
    tree[rt].pre = pre;
    tree[rt].size = 1;
    tree[rt].val = val;
    tree[rt].add = 0;
    tree[rt].sum = val;
    tree[rt].rev = tree[rt].same = 0;
    tree[rt].ch[0] = tree[rt].ch[1] = 0;
    tree[rt].lx = tree[rt].rx = tree[rt].mx = val;
}

void buildTree(int &cur, int l, int r, int pre, int *a){
    if(l > r) return;
    int mid = (l + r) >> 1;
    newNode(cur, pre, a[mid]);
    buildTree(tree[cur].ch[0], l, mid - 1, cur, a);
    buildTree(tree[cur].ch[1], mid + 1, r, cur, a);
    pushUp(cur);
}

void init(int *data){

    root = total = 0;
    while(!mPool.empty()) mPool.pop();
    tree[root].rev = tree[root].same = 0;
    tree[root].ch[0] = tree[root].ch[1] = 0;
    tree[root].lx = tree[root].rx = tree[root].mx = -INF;
    tree[root].sum = tree[root].add = tree[root].val = 0;
    tree[root].pre = tree[root].size = tree[root].sum = 0;

    newNode(root, 0, -1);                           // 注1
    newNode(tree[root].ch[1], root, -1);            // 注2

    buildTree(key_value, 0, n - 1, tree[root].ch[1], data);

    pushUp(tree[root].ch[1]);
    pushUp(root);
}

注1和注2插入了两个多余的结点，无论对树进行什么操作，这两个节点 总是 一个在 树的根的上面， 一个在树的最右子树的叶节点。 插入这两个节点的原因是，有这两个节点时可以避免讨论父节点是否是根节点，和叶节点是否是最右节点这两种情况。这两种情况都是特殊情况，正常情况下应该进行讨论。这种思想类似于无头链表和有头链表，可以去了解一下。

旋转

伸展树的大部分操作是以旋转为基础的，伸展树最重要的也是它的旋转操作，旋转操作一般有三组共六种操作，下面来讲一下这些旋转操作:

单旋

当目标节点是根节点的左子节点或右子节点时，进行一次单旋转，将目标节点调整到根节点的位置。
右旋
左旋

一字型双旋

节点 A 的父节点 B 不是根节点，B 的父节点为 C，且 A 与 B 同时是各自父节点的左孩子或者同时是各自父节点的右孩子。这时，我们进行一次左左旋转操作或者右右旋转操作。

一字型双右旋

一字型双右旋

一字型双左旋

一字型双左旋

之字型双旋

节点 A 的父节点 B 不是根节点，B 的父节点为 C ， A 与 B 中一个是其父节点的左孩子而另一个是其父节点的右孩子。这时，我们进行一次左右旋转操作或者右左旋转操作。

之字型先右后左

之字型先右后左

之字型先左后右

之字型先左后右

参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// 实现单旋
// com == 0 时， 对 cur 节点进行左旋
// com == 1 时， 对 cur 节点进行右旋
void rotate(int cur, int com){
    int pre = tree[cur].pre;
    pushDown(pre);
    pushDown(cur);

    tree[pre].ch[!com] = tree[cur].ch[com];
    tree[tree[cur].ch[com]].pre = pre;

    /* 上面的语句可以展开成下面的语句
    if(com){
        tree[pre].ch[0] = tree[cur].ch[1];    
        tree[tree[cur].ch[1]].pre = pre;
    }else{
        tree[pre].ch[1] = tree[cur].ch[0];   
        tree[tree[cur].ch[0]].pre = pre;
    }
    */

    if(tree[pre].pre){
        tree[tree[pre].pre].ch[tree[tree[pre].pre].ch[1] == pre] = cur;
    }

    tree[cur].pre = tree[pre].pre;
    tree[cur].ch[com] = pre;
    tree[pre].pre = cur;
    pushUp(pre);
}

// 实现树的调整
// 将 rt 节点调整到 tar 下面
void splay(int rt, int tar){
    pushDown(rt);
    while(tree[rt].pre != tar){
        if(tree[tree[rt].pre].pre == tar){
            pushDown(tree[rt].pre);
            pushDown(rt);
            rotate(rt, tree[tree[rt].pre].ch[0] == rt);
        }else{
            pushDown(tree[tree[rt].pre].pre);
            pushDown(tree[rt].pre);
            pushDown(rt);
            int pre = tree[rt].pre;
            int com = tree[tree[pre].pre].ch[0] == pre;
            if(tree[pre].ch[com] == rt){
                rotate(rt, !com);
                rotate(rt, com);
            }else{
                rotate(pre, com);
                rotate(rt, com);
            }
        }
    }
    pushUp(rt);
    if(tar == 0) root = rt;
}

获取某个值

通常 splay 树的操作都是先得到一个数，然后以此作为基本再进行其他操作。

获取第 k 个数

可以通过左右子树的大小获得:
参考代码:

1
2
3
4
5
6
7
int getKth(int rt, int k){
    pushDown(rt);
    int tmp = tree[tree[rt].ch[0]].size + 1;
    if(tmp == k) return rt;
    else if(tmp > k) return getKth(tree[rt].ch[0], k);
    else return getKth(tree[rt].ch[1], k - tmp);
}

获得大于 val 的最小数位置

此操作基于树的中序遍历是一个不减序列，通过遍历树可求得
参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int getValMinPos(int rt, int val){
    int Min = INF;
    int pos = -1;
    while(rt){
        pushDown(rt);
        if(tree[rt].val == val) return rt;
        if(tree[rt].val > a){
            if(Min > tree[rt].val){
                Min = tree[rt].val;
                pos = rt;
            }
            rt = tree[rt].ch[0];
        }
        else rt = tree[rt].ch[1];
    }
    return pos;
}

同理可得小于 val 的最大值.

获取值为 val 的数的排名

此操作基于 splay 树中的值唯一，且树的中序遍历是一个不减序列.
先遍历整棵树，找到 val 的位置，然后将 val 旋转到 root 位置， 然后 root 的左子树的 size + 1 即所求.
参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

// 得到 val 的位置
int getValPos(int rt, int val){
    if(rt == 0) return -1;
    if(tree[rt].val == val) return rt;
    else if(tree[rt].val > val)
        return getValPos(tree[rt].ch[0], val);
    else
        return getValPos(tree[rt].ch[1], val);
}

int getValRank(int rt, int val){
    int pos = getValPos(root, val);
    splay(pos, 0);
    int res = 0;
    if(tree[root].ch[0]) res += tree[tree[root].ch[0]].size;
    res += 1;
    return res;
}

获取最小数的位置

此操作基于树的中序遍历是一个不减序列;
参考代码:

1
2
3
4
5
6
7
8
int getMin(int rt){
    pushDown(rt);
    while(tree[rt].ch[0]){
        rt = tree[rt].ch[0];
        pushDown(rt);
    }
    return rt;
}

获取最大数的位置

此操作基于树的中序遍历是一个不减序列;
参考代码:

1
2
3
4
5
6
7
8
int getMax(int rt){
    pushDown(rt);
    while(tree[rt].ch[1]){
        rt = tree[rt].ch[1];
        pushDown(rt);
    }
    return rt;
}

插入

插入元素是树的基本操作， 方法是根据建树时所遵循的元素顺序，将 key 插入至树中合适的叶子节点上(比如元素从小到大排列时合适的顺序等)。

以在 x 个数后面插入 val 为例:
先把第 x 个数旋转到 root 位置，然后将第 x + 1 个数旋转到 root 的右儿子 的位置，此时只需把将要插入的数插入到 root左儿子 位置即可.

参考代码:

1
2
3
4
5
6
7
8
// 在第 x 个数后面插入 val
void insertOne(int x, int val){
    splay(getKth(root, x + 1), 0);
    splay(getKth(root, x + 2), root);
    newNode(key_value, tree[root].ch[1], val);
    pushUp(tree[root].ch[1]);
    pushUp(root);
}

删除

以删除第 k 个数为例:
先将第 k - 1 个数调整到 root 位置， 再将 k + 1 个数调整到 root 的右儿子，则第 k 个数在 root 的右儿子的左儿子 的位置。

参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 回收内存
void erase(int rt){
    if(rt){
        mPool.push(rt);
        erase(tree[rt].ch[0]);
        erase(tree[rt].ch[1]);   
    }
}

// 删除第 k 个数
void deleteOne(int k){
    splay(getKth(root, k), 0);
    splay(getKth(root, k + 2), root);
    erase(key_value);
    tree[key_value].pre = 0;
    key_value = 0;
    pushUp(tree[root].ch[1]);
    pushUp(root);
}

拓展操作

拓展操作是基本操作的各种组合形成的，现在讨论几个典型的示例.

区间操作

** 问题1：** 在某个点 L 后插入连续一段区间
** 解答: **
将 pos 旋转至根节点，再将 （L+1） 旋转至根节点的右子节点处。在 （L+1） 的左子节点进行逐个插入。
区间插入

参考代码:

1
2
3
4
5
6
7
8
// 从第 pos 个数后开始插入 val 数组中的数
void insert(int pos, int cnt, int *val){
    splay(getKth(root, pos + 1), 0);
    splay(getKth(root, pos + 2), root);
    buildTree(key_value, 0, cnt - 1, tree[root].ch[1], val);
    pushUp(tree[root].ch[1]);
    pushUp(root);
}

** 问题2：** 删除一段连续区间 [L,R]：
** 解答: **
将节点 （L-1） 旋转至根节点，再将 （R+1） 旋转至 (L-1) 的右子节点处。此时 （R+1） 的左子树就是区间 [L，R]。
将整棵左子树删除即可。
区间删除

参考代码：

1
2
3
4
5
6
7
8
9
10
// 从 pos 个数开始连续删除 cnt 个数
void Delete(int pos, int cnt){
    splay(getKth(root, pos), 0);
    splay(getKth(root, pos + cnt + 1), root);
    erase(key_value);
    tree[key_value].pre = 0;
    key_value = 0;
    pushUp(tree[root].ch[1]);
    pushUp(root);
}

** 问题3：** 求区间[L,R]所有元素的和
** 解答: **
将节点 （L-1） 旋转至根节点，再将 （R+1） 旋转至 (L-1) 的右子节点处。此时 （R+1） 的左子树就是区间 [L，R]。左子树的根节点的 sum 就是所求结果。
区间求和

参考代码:

1
2
3
4
5
6
// 获取 [l, r] 的和
int getSum(int l, int r){
    splay(getKth(root, l), 0);
    splay(getKth(root, r + 2), root);
    return tree[key_value].sum;
}

** 问题4：** 区间更新
** 解答: **
将节点 （L-1） 旋转至根节点，再将 （R+1） 旋转至 (L-1) 的右子节点处。此时 （R+1） 的左子树就是区间 [L，R] 。更新整棵左子树。（若更新操作过多，可使用类似于线段树的延迟标记）。
区间更新

参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 将 [l, r] 区间的所有值都增加 val
void makeAdd(int l, int r, int val){
    splay(getKth(root, l), 0);
    splay(getKth(root, r + 2), root);
    updateAdd(key_value, val);
    pushUp(tree[root].ch[1]);
    pushUp(root);
}

// 从 pos 开始的连续 cnt 个数都更改为 val
void makeSame(int pos, int cnt, int val){
    splay(getKth(root, pos), 0);
    splay(getKth(root, pos + cnt + 1), root);
    updateSame(key_value, val);
    pushUp(tree[root].ch[1]);
    pushUp(root);
}

** 问题5：** 区间循环滑动
假设原来的区间为 [L, R], 区间中的数值为[2, 3, 4, 5], 现在将其循环滑动 3 次， 则序列变为 [3, 4, 5, 2];
** 解答: **
将节点 （L-1） 旋转至根节点，再将 （R+1） 旋转至 (L-1) 的右子节点处。此时 （R+1） 的左子树就是区间 [L，R]。假设滑动后的区间为 [l,R,L,r] (对应在原来区间中的位置为 [L,r,l,R])。
将 r 节点旋转至 （R+1） 左子树的根节点。再将 R 旋转至 r 节点的右子树的根节点。然后搬移两颗子树即可.
区间滑动
区间滑动

参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 将 [l, r] 区间循环右移 T 个单位
void revolve(int l, int r, int T){
    int len = r - l + 1;
    T = (T % len + len) % len;
    if(T == 0) return;
    int c = r - T + 1;
    splay(getKth(root, c), 0);
    splay(getKth(root, r + 2), root);
    int tmp = key_value;
    key_value = 0;
    pushUp(tree[root].ch[1]);
    pushUp(root);
    splay(getKth(root, l), 0);
    splay(getKth(root, l + 1), root);
    key_value = tmp;
    tree[key_value].pre = tree[root].ch[1];
    pushUp(tree[root].ch[1]);
    pushUp(root);
}

** 问题6：** 区间反转
** 解答: **
将节点 （L-1） 旋转至根节点，再将 （R+1） 旋转至 (L-1) 的右子节点处。此时 （R+1） 的左子树就是区间 [L，R]。然后依次交换左右子树即可。（也可使用延迟标记）
区间反转
区间反转

参考代码：

1
2
3
4
5
6
7
void reverse(int l, int r){
    splay(getKth(root, l), 0);
    splay(getKth(root, r + 2), root);
    updateRev(key_value);
    pushUp(tree[root].ch[1]);
    pushUp(root);
}

** 问题7：** 区间子序列最大的和
** 解答: **
每个节点维护三个值。区间 [L,R] 表示以节点 i 为根节点的子树的区间。lx[i] 表示以 L 为左起点的子序列的最大和。
rx[i] 表示以 R 为右结尾的子序列的最大和。mx[i] 表示区间子序列最大和。
mx 可由 子节点的值转移而来: (转移的过程发生在树结构或者节点值发生变化时)

1
2
3
4
lx[i] = max(lx[lson],sum[lson] + key[i] + max(0,lx[rson]));
rx[i] = max(rx[rson],sum[rson] + key[i] + max(0,rx[lson]));
mx[i] = max(0,rx[lson]) + key[i] + max(0,lx[rson]);
mx[i] = max(mx[i],max(mx[lson],mx[rson]));

有了这个 mx 值。就可以将节点 （L-1） 旋转至根节点，再将 （R+1） 旋转至 (L-1) 的右子节点处。此时 （R+1） 的左子树就是区间 [L，R]。
左子树的根节点的 mx 值就是所求的。
区间子序列最大的和

参考代码:

1
2
3
4
5
6
// 从 pos 开始连续 cnt 长度的区间内子序列的最大和
int getMaxSum(int pos, int cnt){
    splay(getKth(root, pos), 0);
    splay(getKth(root, pos + cnt + 1), root);
    return tree[key_value].mx;
}

总结

跟线段树相同，根据题目要求splay维护的东西也不同，需要按照题目要求来自行修改。在懂得splay树的操作之后，在重要的是利用他的这些特性来快速的解决问题，比如怎么旋转之后可以快速放方便的得到结果等等。
下面是一份完整的代码，综合了目前见过的一些需要维护的东西。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
/*=============================================================================
# author:            Andrewei
# last modified:     2016-07-12 08:22
# filename:          a.cpp
# description: 
=============================================================================*/

#include <set>
#include <map>
#include <cmath>
#include <stack>
#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define key_value tree[tree[root].ch[1]].ch[0]
// 定义了一个宏，代表根节点的右儿子的左儿子，我们在进行操作时都会尽量把数据集中在这个地方
const int maxn = 500010;                    // 数据规模
const int INF = (1 << 29);                  // 定义了一个极大值
struct Node{
    int ch[2];                              // 左右儿子
    int pre, val, size;                     // 父节点，当前节点的值，当前节点为根的子树的大小
    long long sum;                          // 当前节点为根的子树的和

    int rev, add, same;                     // 反转标记, 增量延迟标记， 区间所有元素相同标记
    int lx, rx, mx;                         // 从区间最左端开始的子序列最大和，从区间最右端开始的区间子序列最大和，整个区间里面子序列最大和
};

int root, total;                            // 根节点，节点数量
stack <int> mPool;                          // 内存池，用来存储删除节点时释放的节点, 以便之后使用
Node tree[maxn];                            // 树的所有节点

int n, q;                                   // n 个数， q 个询问
int data[maxn];                             // 原始数据

// 更新增量延迟标记
void updateAdd(int rt, int add){
    if(!rt) return;
    tree[rt].add += add;
    tree[rt].val += add;
    tree[rt].sum += (long long)add * tree[rt].size;
}

// 更新反转延迟标记
void updateRev(int rt){
    if(!rt) return;
    tree[rt].rev ^= 1;
    swap(tree[rt].lx, tree[rt].rx);
    swap(tree[rt].ch[0], tree[rt].ch[1]);
}

// 更新区间元素值相同延迟标记
void updateSame(int rt, int val){
    if(!rt) return;
    tree[rt].val = val;
    tree[rt].sum = val * tree[rt].size;
    tree[rt].lx = tree[rt].rx = tree[rt].mx = max(val, val * tree[rt].size);
    tree[rt].same = 1;
}

// 通过孩子节点的数据来更新父节点的数据
void pushUp(int rt){
    int lson = tree[rt].ch[0], rson = tree[rt].ch[1];

    // 更新节点的大小
    tree[rt].size = tree[lson].size + tree[rson].size + 1;

    // 更新该节点及其子树所有值的和
    tree[rt].sum = tree[lson].sum + tree[rson].sum + tree[rt].val;

    // 更新子序列最大值
    tree[rt].lx = max((long long)tree[lson].lx, tree[lson].sum + tree[rt].val + max(0, tree[rson].lx));
    tree[rt].rx = max((long long)tree[rson].rx, tree[rson].sum + tree[rt].val + max(0, tree[lson].rx));
    tree[rt].mx = max(0, tree[lson].rx) + tree[rt].val + max(0, tree[rson].lx);
    tree[rt].mx = max(tree[rt].mx, max(tree[lson].mx, tree[rson].mx));
}

// 将父节点的延迟标记更新到孩子节点
void pushDown(int rt){

    // 更新增量延迟标记
    if(tree[rt].add){
        updateAdd(tree[rt].ch[0], tree[rt].add);
        updateAdd(tree[rt].ch[1], tree[rt].add);
        tree[rt].add = 0;
    }

    // 更新区间相同标记
    if(tree[rt].same){
        updateSame(tree[rt].ch[0], tree[rt].val);
        updateSame(tree[rt].ch[1], tree[rt].val);
        tree[rt].same = 0;
    }

    // 更新反转标记
    if(tree[rt].rev){
        updateRev(tree[rt].ch[0]);
        updateRev(tree[rt].ch[1]);
        tree[rt].rev = 0;
    }
}

void newNode(int &rt, int pre, int val){
    if(!mPool.empty()){
        rt = mPool.top();
        mPool.pop();
    }else{
        rt = ++total;
    }
    tree[rt].pre = pre;
    tree[rt].size = 1;
    tree[rt].val = val;
    tree[rt].add = 0;
    tree[rt].sum = val;
    tree[rt].rev = tree[rt].same = 0;
    tree[rt].ch[0] = tree[rt].ch[1] = 0;
    tree[rt].lx = tree[rt].rx = tree[rt].mx = val;
}

void buildTree(int &cur, int l, int r, int pre, int *a){
    if(l > r) return;
    int mid = (l + r) >> 1;
    newNode(cur, pre, a[mid]);
    buildTree(tree[cur].ch[0], l, mid - 1, cur, a);
    buildTree(tree[cur].ch[1], mid + 1, r, cur, a);
    pushUp(cur);
}

void init(int *data){

    root = total = 0;
    while(!mPool.empty()) mPool.pop();
    tree[root].rev = tree[root].same = 0;
    tree[root].ch[0] = tree[root].ch[1] = 0;
    tree[root].lx = tree[root].rx = tree[root].mx = -INF;
    tree[root].sum = tree[root].add = tree[root].val = 0;
    tree[root].pre = tree[root].size = tree[root].sum = 0;

    newNode(root, 0, -1);                           // 注1
    newNode(tree[root].ch[1], root, -1);            // 注2

    buildTree(key_value, 0, n - 1, tree[root].ch[1], data);

    pushUp(tree[root].ch[1]);
    pushUp(root);
}

// 实现单旋
// com == 0 时， 对 cur 节点进行左旋
// com == 1 时， 对 cur 节点进行右旋
void rotate(int cur, int com){
    int pre = tree[cur].pre;
    pushDown(pre);
    pushDown(cur);

    tree[pre].ch[!com] = tree[cur].ch[com];
    tree[tree[cur].ch[com]].pre = pre;

    /* 上面的语句可以展开成下面的语句
    if(com){
        tree[pre].ch[0] = tree[cur].ch[1];    
        tree[tree[cur].ch[1]].pre = pre;
    }else{
        tree[pre].ch[1] = tree[cur].ch[0];   
        tree[tree[cur].ch[0]].pre = pre;
    }
    */

    if(tree[pre].pre){
        tree[tree[pre].pre].ch[tree[tree[pre].pre].ch[1] == pre] = cur;
    }

    tree[cur].pre = tree[pre].pre;
    tree[cur].ch[com] = pre;
    tree[pre].pre = cur;
    pushUp(pre);
}

// 实现树的调整
// 将 rt 节点调整到 tar 下面
void splay(int rt, int tar){
    pushDown(rt);
    while(tree[rt].pre != tar){
        if(tree[tree[rt].pre].pre == tar){
            pushDown(tree[rt].pre);
            pushDown(rt);
            rotate(rt, tree[tree[rt].pre].ch[0] == rt);
        }else{
            pushDown(tree[tree[rt].pre].pre);
            pushDown(tree[rt].pre);
            pushDown(rt);
            int pre = tree[rt].pre;
            int com = tree[tree[pre].pre].ch[0] == pre;
            if(tree[pre].ch[com] == rt){
                rotate(rt, !com);
                rotate(rt, com);
            }else{
                rotate(pre, com);
                rotate(rt, com);
            }
        }
    }
    pushUp(rt);
    if(tar == 0) root = rt;
}

int getKth(int rt, int k){
    pushDown(rt);
    int tmp = tree[tree[rt].ch[0]].size + 1;
    if(tmp == k) return rt;
    else if(tmp > k) return getKth(tree[rt].ch[0], k);
    else return getKth(tree[rt].ch[1], k - tmp);
}

int getValMinPos(int rt, int val){
    int Min = INF;
    int pos = -1;
    while(rt){
        pushDown(rt);
        if(tree[rt].val == val) return rt;
        if(tree[rt].val > val){
            if(Min > tree[rt].val){
                Min = tree[rt].val;
                pos = rt;
            }
            rt = tree[rt].ch[0];
        }
        else rt = tree[rt].ch[1];
    }
    return pos;
}

// 得到 val 的位置
int getValPos(int rt, int val){
    if(!rt) return -1;
    if(tree[rt].val == val) return rt;
    else if(tree[rt].val > val)
        return getValPos(tree[rt].ch[0], val);
    else
        return getValPos(tree[rt].ch[1], val);
}

int getValRank(int rt, int val){
    int pos = getValPos(root, val);
    splay(pos, 0);
    int res = 0;
    if(tree[root].ch[0]) res += tree[tree[root].ch[0]].size;
    res += 1;
    return res;
}

int getMin(int rt){
    pushDown(rt);
    while(tree[rt].ch[0]){
        rt = tree[rt].ch[0];
        pushDown(rt);
    }
    return rt;
}

int getMax(int rt){
    pushDown(rt);
    while(tree[rt].ch[1]){
        rt = tree[rt].ch[1];
        pushDown(rt);
    }
    return rt;
}

// 在第 x 个数后面插入 val
void insertOne(int x, int val){
    splay(getKth(root, x + 1), 0);
    splay(getKth(root, x + 2), root);
    newNode(key_value, tree[root].ch[1], val);
    pushUp(tree[root].ch[1]);
    pushUp(root);
}

// 回收内存
void erase(int rt){
    if(rt){
        mPool.push(rt);
        erase(tree[rt].ch[0]);
        erase(tree[rt].ch[1]);   
    }
}

// 删除第 k 个数
void deleteOne(int k){
    splay(getKth(root, k), 0);
    splay(getKth(root, k + 2), root);
    erase(key_value);
    tree[key_value].pre = 0;
    key_value = 0;
    pushUp(tree[root].ch[1]);
    pushUp(root);
}

// 从第 pos 个数后开始插入 val 数组中的数
void insert(int pos, int cnt, int *val){
    splay(getKth(root, pos + 1), 0);
    splay(getKth(root, pos + 2), root);
    buildTree(key_value, 0, cnt - 1, tree[root].ch[1], val);
    pushUp(tree[root].ch[1]);
    pushUp(root);
}

// 从 pos 个数开始连续删除 cnt 个数
void Delete(int pos, int cnt){
    splay(getKth(root, pos), 0);
    splay(getKth(root, pos + cnt + 1), root);
    erase(key_value);
    tree[key_value].pre = 0;
    key_value = 0;
    pushUp(tree[root].ch[1]);
    pushUp(root);
}

// 获取 [l, r] 的和
int getSum(int l, int r){
    splay(getKth(root, l), 0);
    splay(getKth(root, r + 2), root);
    return tree[key_value].sum;
}

// 将 [l, r] 区间循环右移 T 个单位
void revolve(int l, int r, int T){
    int len = r - l + 1;
    T = (T % len + len) % len;
    if(T == 0) return;
    int c = r - T + 1;
    splay(getKth(root, c), 0);
    splay(getKth(root, r + 2), root);
    int tmp = key_value;
    key_value = 0;
    pushUp(tree[root].ch[1]);
    pushUp(root);
    splay(getKth(root, l), 0);
    splay(getKth(root, l + 1), root);
    key_value = tmp;
    tree[key_value].pre = tree[root].ch[1];
    pushUp(tree[root].ch[1]);
    pushUp(root);
}

void reverse(int l, int r){
    splay(getKth(root, l), 0);
    splay(getKth(root, r + 2), root);
    updateRev(key_value);
    pushUp(tree[root].ch[1]);
    pushUp(root);
}

void makeSame(int pos, int cnt, int val){
    splay(getKth(root, pos), 0);
    splay(getKth(root, pos + cnt + 1), root);
    updateSame(key_value, val);
    pushUp(tree[root].ch[1]);
    pushUp(root);
}

// 将 [l, r] 区间的所有值都增加 val
void makeAdd(int l, int r, int val){
    splay(getKth(root, l), 0);
    splay(getKth(root, r + 2), root);
    updateAdd(key_value, val);
    pushUp(tree[root].ch[1]);
    pushUp(root);
}


// 从 pos 开始连续 cnt 长度的区间内子序列的最大和
int getMaxSum(int pos, int cnt){
    splay(getKth(root, pos), 0);
    splay(getKth(root, pos + cnt + 1), root);
    return tree[key_value].mx;
}

int main(){
    int x, y, z;
    char op[20];
    while(scanf("%d%d", &n, &q) != EOF){
        for(int i = 0; i < n; i++){
            scanf("%d", &data[i]);
        }
        init(data);
        while(q--){
            scanf("%s", op);
            if(op[0] == 'I'){
                scanf("%d%d", &x, &y);
                for(int i = 0; i < y; i++)
                    scanf("%d", &data[i]);
                insert(x, y, data);
            }else if(op[0] == 'D'){
                scanf("%d%d", &x, &y);
                Delete(x, y);
            }else if(op[0] == 'M' && op[2] == 'K'){
                scanf("%d%d%d", &x, &y, &z);
                makeSame(x, y, z);
            }else if(op[0] == 'R'){
                scanf("%d%d", &x, &y);
                reverse(x, x + y - 1);
            }else if(op[0] == 'G'){
                scanf("%d%d", &x, &y);
                printf("%d\n", getSum(x, x + y - 1));
            }else{
                printf("%d\n", getMaxSum(1, tree[root].size - 2));
            }
        }
    }
    return 0;
}