跳转至

Fhq-Treap

最近有点咕咕咕，学了东西不咋想写笔记想学点更多的。

数据结构这种东西真的很难让人提起欲望，难过，当然也能是那天早上没晨跑导致太困了。

我学习的顺序是 Treap -> Splay -> FHQ Treap，个人觉得 Splay 其实不难理解，但是第一次看的话的确是 FHQ 好理解的多。

而且 FHQ 代码也确实看起来更清爽一点（可能我比较喜欢略微紧凑的代码），相对于 Splay 来说也更好写。

Splay 其实可能更多的会拿去写 LCT，FHQ Treap 直观，常数略大，但是可以可持久化，整体看着比较爽（）

泛化ψ(｀∇´)ψ

虽然以前了解过平衡树，有对基本概念的理解，不过还是先放一下比较好（结构要完整）

首先对于一颗二叉树，定义两个重要的东西。

  • 堆性质：满足对于任意节点 \(u\)，父亲的权值不小于儿子的权值。
  • BST： 对于任意节点 \(u\)，它的左子树中节点的关键码都小于它，右子树中都大于它的二叉树被称作 Binary search tree。

同时满足以上两个性质的二叉树被称作笛卡尔树（Cartesian tree）。

而 Treap 就是一颗笛卡尔树。

众所周知 BST 的形态并不唯一，它可以是一条链，也可以是接近满二叉树那样紧凑的结构。

显然对于一颗 BST，我们希望上面每个节点的深度越低越好，因为在 BST 上插入，删除，排名等操作的复杂度都是 \(O(d)\) 的。

那么通过一些方式动态维护，使得 \(d\) 尽量小的数据结构就可以被称作平衡树。

Treap 的核心思想是通过产生一个随机权值 \(rd\)，满足堆性质，对整棵树进行动态维护以达到平衡。

Treap 的维护方式是通过旋转，但是 FHQ Treap 有更加简洁的方式，合并和分裂，不仅不需要旋转，还能更加方便的支持区间操作和可持久化。

通常来说 FHQ Treap 的操作都可以规约成，将需要操作的位置/区间从树当中分离出来，进行操作，然后把树合并回去，仍然满足笛卡尔树的性质。

下面将结合三/四道例题对 FHQ Treap 的操作进行说明，本文的思想，代码，均参考了 Charleswu 的 FHQTreap 学习笔记，并在其上有所补充，在此感谢。

基本操作ψ(｀∇´)ψ

本部分例题：普通平衡树, AC Code。

Definitions 定义ψ(｀∇´)ψ

使用 C++ Class 进行封装，树上每个节点维护以下的几个信息：

一并附有一些简单的基本操作

 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
using i64 = long long;
using u64 = unsigned long long;

const int si = 1e5 + 10;

u64 inf;
i64 overv = 1ll << 60; // 越界值，作为错误返回信息
std::mt19937_64 rnd(time(0));

class fhqTreap {
  private:
    int tot; // 节点个数
    struct Node {
        u64 pri; // 随机权值
        int val, cnt, siz, ls, rs;
        // 关键码，副本数，子树大小，左右儿子编号。
    } t[si];
    int newNode(int val) {
        t[++tot] = (Node){rnd(), val, 1, 1, 0, 0};
        return tot;
    } // 新建节点
    void maintain(int p) {
        t[p].siz = t[t[p].ls].siz + t[t[p].rs].siz + t[p].cnt;
    } // 类似于 pushup，在形态改变或者是信息改变时更新。
  public: 
    int rt; // 根节点
    void init() { rt = tot = 0; t[0] = {inf, 0, 0, 0, 0, 0}; } // 初始化
} tr;

Split 分裂ψ(｀∇´)ψ

FHQ Treap 的分裂分为两种，一种是按权值分裂，一种是按子树大小分裂。

前者主要用于维护值域时，后者主要用于维护序列时。

但是两者的本质都是，将原 Treap 按照一定条件分裂成两个新的 Treap。

以按权值分裂为例，我们现在需要将原 Treap 分裂为两个 Treap \(A, B\)，其中 \(\forall x \in A, val(x) \le k, \forall y \in B, val(x) > k\)。

做法很简单，比较像线段树二分，如果注意到当前节点 \(p\) 的权值 \(val(p)\) 已经小于等于 \(k\) 了，那么说明这个节点和它的左子树都应当属于 \(A\)，而右子树当中有一些部分属于 \(A\)。

我们递归的分裂右子树即可，反过来，如果 \(val(p) > k\)，那么递归分裂左子树即可。

代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
// 返回 A, B 两个 Treap 的根节点编号构成的 pair。
std::pair<int, int> split(int p, int key) {
    if(!p) return make_pair(0, 0); // 注意判边界。
    if(t[p].val <= key) {
        auto o = split(t[p].rs, key); // 递归分裂。
        t[p].rs = o.first, maintain(p); // 形态已经改变，需要 maintain。
        return make_pair(p, o.second);
    } 
    else {
        auto o = split(t[p].ls, key);
        t[p].ls = o.second, maintain(p);
        return make_pair(o.first, p);
    }
}

用图来解释就是：

fhq-1

按子树大小分裂也比较类似，不过要注意比较的时候是 t[p].siz + t[p].cnt，并且要对 \(lim\) 做减法。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
std::pair<int, int> split(int p, int lim) {
    if(!p) return make_pair(0, 0);
    if(t[t[p].ls].siz + 1 <= lim) {
        auto o = split(t[p].rs, lim - t[t[p].ls].siz - 1);
        t[p].rs = o.first, maintain(p);
        return make_pair(p, o.second);
    }
    else {
        auto o = split(t[p].ls, lim);
        t[p].ls = o.second, maintain(p);
        return make_pair(o.first, p);
    }
}

Merge 合并ψ(｀∇´)ψ

合并也比较类似，对给定的两个已经相对满足 Treap 性质的 Treap \(A, B\) 进行合并。

因为它们本身是 Treap，并且关键码也相对满足了 BST 性质，那么我们要做的就是维护堆性质。

维护两个指针向下，令随机权值大的作为子树的根，另一边递归合并即可，注意要满足 BST 性质。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
// 返回以 p q 为根的 Treap 合并后的根节点。
int merge(int p, int q) {
    if(!p || !q) return p ^ q; // 这么写比分开写好，不容易出现 !p return p 的错误。
    if(t[p].pri >= t[q].pri) {
        t[p].rs = merge(t[p].rs, q);
        maintain(p); return p;
    }
    else {
        t[q].ls = merge(p, t[q].ls);
        maintain(q); return q;
    }
}

Insert 插入ψ(｀∇´)ψ

来点 FHQ 特色.jpg

这里说的是对值域插入。

我们可以直接对原有 Treap 进行分裂。

分裂出三颗子 Treap，一边是 \(val < x\) 的，一边是 \(val > x\) 的，\(val = x\) 的在中间。

子树可能为空，这不要紧，我们只关心中间的那个，如果为空就新建，不为空新增副本。

也有写法是直接新建，不过我为了效率和空间习惯于直接增加副本。

1
2
3
4
5
6
7
8
void insert(int val) {
    auto o = split(rt, val);
    auto p = split(o.first, val - 1);
    if(!p.second) 
        p.second = newNode(val);
    else t[p.second].cnt++, t[p.second].siz++;
    rt = merge(merge(p.first, p.second), o.second);
}

插入完记得 Merge 回去。

当然如果是维护序列，我们一般就考虑直接利用笛卡尔树的性质 \(O(n)\) 建树，这个暂时还没写，咕咕。

Delete 删除ψ(｀∇´)ψ

和 Insert 差不多，直接找到对应位置考虑一下就行。

但是要注意判空，并且可持久化的时候如果要用内存回收，可能这个版本虽然被删了，但是之后的版本仍然依赖它，这个是需要注意的。

1
2
3
4
5
6
7
8
void insert(int val) {
    auto o = split(rt, val);
    auto p = split(o.first, val - 1);
    if(!p.second) 
        p.second = newNode(val);
    else t[p.second].cnt++, t[p.second].siz++;
    rt = merge(merge(p.first, p.second), o.second);
}

Rank 查询排名ψ(｀∇´)ψ

直接按值分出一个 \(val < x\) 的子树 \(p\)。

排名就是 \(siz(p) + 1\)，这里其实还是需要判一下是不是在子树里面可能，不过全都比它小不用判。

1
2
3
4
5
6
int rank(int val) {
    auto o = split(rt, val - 1);
    int ret = t[o.first].siz + 1;
    rt = merge(o.first, o.second);
    return ret;
}

Kth 查询第 K 大ψ(｀∇´)ψ

因为按权值分裂不好弄，所以直接按照正常 BST 写法来了。

记得判不存在的情况。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
i64 kth(int p, int k) {
    if(t[p].siz < k) return overv;
    if(t[t[p].ls].siz >= k)
        return kth(t[p].ls, k);
    else {
        if(t[p].cnt + t[t[p].ls].siz >= k)
            return 1ll * t[p].val;
        else return kth(t[p].rs, k - (t[p].cnt + t[t[p].ls].siz));
    }
}

这里值域是 int，所以用了 long long 来判越界。

Prev Next 前驱后继ψ(｀∇´)ψ

分裂出来之后用 kth 做一下就好了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
i64 pre(int val) {
    auto o = split(rt, val - 1);
    i64 ret = kth(o.first, t[o.first].siz);
    rt = merge(o.first, o.second);
    return ret;
}
i64 nxt(int val) {
    auto o = split(rt, val);
    i64 ret = kth(o.second, 1);
    rt = merge(o.first, o.second);
    return ret;
}

区间操作ψ(｀∇´)ψ

例题：文艺平衡树，AC Code。

这里开始我们就是在维护序列了，请默认使用子树大小分裂，并且在这里我们不开副本。

维护序列的方式是，以下标作为 BST 的关键码，并且之后，同一个中序遍历的节点维护的是相同的位置的信息，可以发现按子树大小分裂不会影响中序遍历。

线段树维护满足幺半群性质的区间信息操作时，实际上是把节点看作一个一个区间。

这样的数据机构被称作区间树，我们可以把 FHQ Treap 也当作一个区间树，不过这里代表区间的是一个子树罢了。

对于区间操作，我们显然不会直接傻傻的暴力，我们希望类似线段树一样，进行整体的懒操作。

还是打 Tag，注意事项和线段树差不多，不过这里是，在子树形态改变之前就要下放标记，一定要切记这点。

 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
class fhqTreap {
  private:
    int tot = 0;
    struct Node {
        u64 pri;
        int val, siz, ls, rs, tag;
    } t[si];
    int newNode(int val) {
        t[++tot] = (Node){rnd(), val, 1, 0, 0, 0};
        return tot;
    }
    void maintain(int p) {
        t[p].siz = t[t[p].ls].siz + t[t[p].rs].siz + 1;
    }
    void pushdown(int p) { /* do something */}
    std::pair<int, int> split(int p, int lim) {
        if(!p) return make_pair(0, 0);
        pushdown(p);
        if(t[t[p].ls].siz + 1 <= lim) {
            auto o = split(t[p].rs, lim - t[t[p].ls].siz - 1);
            t[p].rs = o.first, maintain(p);
            return make_pair(p, o.second);
        }
        else {
            auto o = split(t[p].ls, lim);
            t[p].ls = o.second, maintain(p);
            return make_pair(o.first, p);
        }
    }
    int merge(int p, int q) {
        if(!p || !q) return p ^ q;
        if(t[p].pri >= t[q].pri) {
            pushdown(p);
            t[p].rs = merge(t[p].rs, q);
            maintain(p); 
            return p;
        }
        else {
            pushdown(q);
            t[q].ls = merge(p, t[q].ls);
            maintain(q);
            return q;
        }
    }
  public:
    int rt;
    void init() {
        rt = tot = 0;
        t[0] = (Node){inf, 0, 0, 0, 0, 0};
    }   
} tr;

Reverse 区间翻转ψ(｀∇´)ψ

可以注意到 BST 维护序列的话，我们按照中序遍历就可以得到原序列。

那么区间反转的本质就是对于区间对应的子树，从上往下递归依次交换左右儿子。

找到区间对应的子树也是简单的，直接分裂两次把区间“剖分”出来就行，这也是 FHQ 好理解好实现的原因之一。

不过这里是按照子树大小分列，limit 会有变化，敬请注意。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
void pushdown(int p) {
    if(!t[p].rev) return;
    swap(t[p].ls, t[p].rs);
    t[t[p].ls].rev ^= 1, t[t[p].rs].rev ^= 1, t[p].rev ^= 1;
}
void rever(int l, int r) {
    auto o = split(rt, l - 1);
    auto p = split(o.second, r - l + 1); // attention!
    t[p.first].rev ^= 1;
    rt = merge(o.first, merge(p.first, p.second));
}

文艺平衡树的权值和关键码（下标）恰好一致，按子树大小分裂直接插入就行，比较方便。

维护数列就需要建笛卡尔树了。

可持久化ψ(｀∇´)ψ

例题：可持久化平衡树，AC Code。

其实比较简单，只需要在有修改的时候复制一下路径就可以了。

要注意版本之间的区分，到底继承哪个版本，删除之后会不会影响之后的依赖？

这题还不需要空间回收，比较良心，因为没啥好说的我就直接贴代码了。

  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
// author : black_trees
// want more regrets?

#include <cmath>
#include <ctime>
#include <cstdio>
#include <random>
#include <cstring>
#include <utility>
#include <iostream>
#include <algorithm>

#define endl '\n'

using namespace std;
using i64 = long long;
using u64 = unsigned long long;

const int si = 5e5 + 10;

u64 inf;
i64 overv = 1ll << 60;
std::mt19937_64 rnd(time(0));

class fhqTreap {
    private:
        int tot;
        struct Node {
            u64 pri;
            int val, cnt, siz, ls, rs;
        } t[si * 50];
        int newNode(int val) {
            t[++tot] = (Node){rnd(), val, 1, 1, 0, 0};
            return tot;
        }
        void maintain(int p) {
            t[p].siz = t[t[p].ls].siz + t[t[p].rs].siz + t[p].cnt;
        }
    public:
        int rt[si << 1], cur = 0;
        void init() { rt[0] = cur = tot = 0; t[0] = {inf, 0, 0, 0, 0, 0}; }
        std::pair<int, int> split(int p, int key) {
            if(!p) return make_pair(0, 0);
            int nw = ++tot;
            t[nw] = t[p];
            if(t[nw].val <= key) {
                auto o = split(t[nw].rs, key);
                t[nw].rs = o.first, maintain(nw);
                return make_pair(nw, o.second);
            } 
            else {
                auto o = split(t[nw].ls, key);
                t[nw].ls = o.second, maintain(nw);
                return make_pair(o.first, nw);
            }
        }
        int merge(int p, int q) {
            if(!p || !q) return p ^ q;
            if(t[p].pri >= t[q].pri) {
                t[p].rs = merge(t[p].rs, q);
                maintain(p); return p;
            }
            else {
                t[q].ls = merge(p, t[q].ls);
                maintain(q); return q;
            }
        }
        void insert(int pr, int val) {
            auto o = split(rt[pr], val);
            auto p = split(o.first, val - 1);
            if(!p.second) 
                p.second = newNode(val);
            else t[p.second].cnt++, t[p.second].siz++;
            rt[++cur] = merge(merge(p.first, p.second), o.second);
        }
        void del(int pr, int val) {
            auto o = split(rt[pr], val);
            auto p = split(o.first, val - 1);
            if(t[p.second].cnt) {
                t[p.second].cnt--, t[p.second].siz--;
                if(t[p.second].cnt) p.first = merge(p.first, p.second);
            }
            rt[++cur] = merge(p.first, o.second);
        }
        int rank(int pr, int val) {
            auto o = split(rt[pr], val - 1);
            int ret = t[o.first].siz + 1;
            rt[++cur] = merge(o.first, o.second);
            return ret;
        }
        i64 kth(int p, int k) {
            if(t[p].siz < k) return overv;
            if(t[t[p].ls].siz >= k)
                return kth(t[p].ls, k);
            else {
                if(t[p].cnt + t[t[p].ls].siz >= k)
                    return 1ll * t[p].val;
                else return kth(t[p].rs, k - (t[p].cnt + t[t[p].ls].siz));
            }
        }
        i64 pre(int pr, int val) {
            auto o = split(rt[pr], val - 1);
            i64 ret = kth(o.first, t[o.first].siz);
            rt[++cur] = merge(o.first, o.second);
            return ret;
        }
        i64 nxt(int pr, int val) {
            auto o = split(rt[pr], val);
            i64 ret = kth(o.second, 1);
            rt[++cur] = merge(o.first, o.second);
            return ret;
        }
} tr;

int main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    int n, op, x, v;

    inf = 0, --inf;

    cin >> n, tr.init();    
    for(int nw = 1; nw <= n; ++nw) {
        cin >> v >> op >> x;
        if(op == 1) tr.insert(v, x);
        if(op == 2) tr.del(v, x);
        if(op == 3) cout << tr.rank(v, x) << endl;
        if(op == 4) cout << tr.kth(tr.rt[v], x) << endl, tr.rt[++tr.cur] = tr.rt[v];
        if(op == 5) {
            i64 ret = tr.pre(v, x);
            if(ret == overv) ret = -2147483647;
            cout << ret << endl;
        }
        if(op == 6) {
            i64 ret = tr.nxt(v, x);
            if(ret == overv) ret = 2147483647;
            cout << ret << endl;
        }
    }
    return 0;
}

进阶区间操作ψ(｀∇´)ψ

维护数列，AC Code。

这道题相比于文艺平衡树，要麻烦了很多，它需要：

  • 维护区间和，全局最大子段和
  • 支持插入/删除一个区间，区间翻转，区间覆盖，询问区间和，询问全局最大子段和。

其实和 GSS3 特别类似，对于最大子段和，我们维护区间的答案，最大前缀和，最大后缀和并更新即可。

对于区间翻转，区间覆盖，我们分别打一个标记就行，可以注意到这两个标记的顺序并不会对答案造成影响。

然后 maintain 和 pushdown 的部分就只需要注意及时更新信息。

插入一个区间可以直接使用笛卡尔树的 \(O(n)\) 建树，最后再从下往上更新信息即可。

这个可能需要解释一下，我顺带就把笛卡尔树笔记写了（比较懒）

笛卡尔树的 \(O(n)\) 建树

假设每个节点维护 \((key, val)\) 两个信息，其中 \(key\) 满足 BST 性质，\(val\) 满足堆性质。

那么我们按照 \(key\) 排序一个一个插入，考虑到每次我们插入的节点都会是原 Treap 最靠右的链上的节点。

于是我们只需要在这个链上找到一个 \(x\) 使得 \(val(x) > val\)，然后我们令新的节点作为 \(x\) 的右子树即可。

原来 \(x\) 的右子树应当作为新节点的左子树，可以发现这个子树的根就是原来在 \(x\) 后面的节点，这个可以单调栈维护。

删除一个区间就直接分裂出来然后删掉，不过这题比较卡空间，需要做一个内存回收，那么删除的时候就需要递归整个子树来删（不过这样似乎没法保证复杂度？）

询问区间和也是直接 split 出来，全局最大子段和只需要树根的信息就行，因为之前的每个操作我们都在子树形态更新前后维护了子树的信息正确性，所以不需要再次遍历整棵树更新了。

但是有一些细节还需要注意，向上传信息的时候，需要考虑左右子树是否为空，这会对最大子段和的更新有影响。

区间覆盖的时候需要特殊处理区间的信息，区间翻转的时候每个节点的前后缀也是会交换的。

另外翻转标记下放的时候前后缀也需要交换，因为区间翻转操作只会打一个 tag，下面的是更新不到的。

  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
// author : black_trees
// want more regrets?

#include <cmath>
#include <ctime>
#include <cstdio>
#include <random>
#include <climits>
#include <cstring>
#include <utility>
#include <iostream>
#include <algorithm>

#define endl '\n'

using namespace std;
using i64 = long long;
using u64 = unsigned long long;

const int si = 5e5 + 10;

u64 inf;
int overv = 1 << 31;
int n, m, a[si];

std::mt19937_64 rnd(time(0));
class fhqTreap {
    private: 
        int top, tp;
        int stk[si], st[si];
        struct Node {
            u64 pri;
            int val, siz, ls, rs;
            int rev, cov, pre, suf, all, sum;
        } t[si];
        int newNode(int val) {
            int nw = stk[top]; top--;
            t[nw] = (Node){rnd(), val, 1, 0, 0, 0, overv, val, val, val, val};
            return nw;
        }
        void maintain(int p) {
            t[p].siz = t[t[p].ls].siz + t[t[p].rs].siz + 1;
            t[p].sum = t[t[p].ls].sum + t[t[p].rs].sum + t[p].val;
            t[p].pre = max({t[t[p].ls].pre, t[t[p].ls].sum + t[p].val + max(t[t[p].rs].pre, 0)});
            t[p].suf = max({t[t[p].rs].suf, max(t[t[p].ls].suf, 0) + t[p].val + t[t[p].rs].sum});
            t[p].all = max(t[t[p].ls].suf, 0) + t[p].val + max(t[t[p].rs].pre, 0);
            if(t[p].ls) t[p].all = max(t[p].all, t[t[p].ls].all);
            if(t[p].rs) t[p].all = max(t[p].all, t[t[p].rs].all);
        }
        void upd(int p) {
            t[p].val = t[p].cov;
            t[p].sum = t[p].siz * t[p].cov;
            t[p].pre = t[p].cov > 0 ? t[p].sum : t[p].val;
            t[p].suf = t[p].cov > 0 ? t[p].sum : t[p].val;
            t[p].all = t[p].cov > 0 ? t[p].sum : t[p].val;
        }
        void pushdown(int p) {
            if(t[p].cov != overv) {
                t[t[p].ls].cov = t[p].cov;
                t[t[p].rs].cov = t[p].cov;
                upd(t[p].ls), upd(t[p].rs);
                t[p].cov = overv;
            }
            if(t[p].rev != 0) {
                swap(t[p].ls, t[p].rs);
                swap(t[t[p].ls].pre, t[t[p].ls].suf);
                swap(t[t[p].rs].pre, t[t[p].rs].suf);
                t[t[p].ls].rev ^= 1, t[t[p].rs].rev ^= 1, t[p].rev ^= 1;
            }
        }
        std::pair<int, int> split(int p, int lim) {
            if(!p) return make_pair(0, 0);
            pushdown(p);
            if(t[t[p].ls].siz + 1 <= lim) {
                auto o = split(t[p].rs, lim - t[t[p].ls].siz - 1);
                t[p].rs = o.first; maintain(p);
                return make_pair(p, o.second);
            }
            else {
                auto o = split(t[p].ls, lim);
                t[p].ls = o.second; maintain(p);
                return make_pair(o.first, p);
            }
        }
        int merge(int p, int q) {
            if(!p || !q) return p ^ q;
            if(t[p].pri >= t[q].pri) {
                pushdown(p);
                t[p].rs = merge(t[p].rs, q);
                maintain(p);
                return p;
            }
            else {
                pushdown(q);
                t[q].ls = merge(p, t[q].ls);
                maintain(q);
                return q;
            }
        }
        void dfs(int u) {
            if(!u) return;
            dfs(t[u].ls), dfs(t[u].rs);
            maintain(u);
        }
        void reset(int u) {
            if(!u) return;
            stk[++top] = u;
            int ls = t[u].ls, rs = t[u].rs;
            reset(ls), reset(rs);
        }
    public:
        int rt, tot;
        void init() {
            inf = 0, --inf, rt = tot = top = 0;
            for(int i = si - 9; i >= 0; --i) {
                stk[++top] = i + 1;
            }
            t[0] = (Node){inf, 0, 0, 0, 0, 0, overv, 0, 0, 0, 0};
        }
        void insert(int pos, int c[], int len) {
            auto o = split(rt, pos);
            int to = 0;
            tp = 0;
            for(int i = 0; i <= len + 1; ++i) {
                st[i] = 0;
            }
            for(int i = 1; i <= len; ++i) {
                int nw = newNode(c[i]);
                to = tp;
                while(to && t[st[to]].pri < t[nw].pri)
                    --to;
                if(to) t[st[to]].rs = nw;
                if(to < tp) t[nw].ls = st[to + 1];
                st[tp = to + 1] = nw;
            }
            dfs(st[1]);
            rt = merge(o.first, merge(st[1], o.second));
        }
        void del(int pos, int len) {
            auto o = split(rt, pos - 1);
            auto p = split(o.second, len);
            reset(p.first);
            rt = merge(o.first, p.second);
        }
        void cover(int pos, int len, int v) {
            auto o = split(rt, pos - 1);
            auto p = split(o.second, len);
            t[p.first].cov = v, upd(p.first);
            rt = merge(o.first, merge(p.first, p.second));
        }
        void rever(int pos, int len) {
            auto o = split(rt, pos - 1);
            auto p = split(o.second, len);
            t[p.first].rev ^= 1;
            swap(t[p.first].pre, t[p.first].suf);
            rt = merge(o.first, merge(p.first, p.second));
        }
        int asksum(int pos, int len) {
            auto o = split(rt, pos - 1);
            auto p = split(o.second, len);
            int ret = t[p.first].sum;
            rt = merge(o.first, merge(p.first, p.second));
            return ret;
        }
        int askmax() {
            return t[rt].all;
        }
} tr;

int main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    cin >> n >> m, tr.init();
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    tr.insert(0, a, n);

    for(int i = 1; i <= m; ++i) {
        string op;
        int l, r, v;
        cin >> op;
        if(op == "INSERT") {
            cin >> l >> r;
            for(int j = 1; j <= r; ++j) {
                cin >> a[j];
            }
            tr.insert(l, a, r);
        }
        if(op == "DELETE") {
            cin >> l >> r;
            tr.del(l, r);
        }
        if(op == "MAKE-SAME") {
            cin >> l >> r >> v;
            tr.cover(l, r, v);
        }
        if(op == "REVERSE") {
            cin >> l >> r;
            tr.rever(l, r);
        }
        if(op == "GET-SUM") {
            cin >> l >> r;
            cout << tr.asksum(l, r) << endl;
        }
        if(op == "MAX-SUM") {
            cout << tr.askmax() << endl;
        }
    }

    return 0;
}
最后更新: September 27, 2023