Rope

Rope 是 C++ STL 中 pb_ds(Policy-Based Data Structures) 库的一个分支，采用可持久化平衡树实现。

在一些需要可持久化数据结构的题目中，可以用于代替实现可持久化平衡树、可持久化线段树（主席树）、可持久化并查集等等。

其插入，删除，访问的时间复杂度都是 O(log(n)) ，拷贝的时间复杂度是 O(1)。

但遗憾的是， Rope 的初衷是作为超级 string 来使用的，尽管底层是可持久化平衡树实现的，但它的功能是被割腌的。

不过，可持久的特性倒是保留了下来，由于 Rope 实例拷贝的时间复杂度是 O(1) ，我们就可以通过保存每个版本来实现可持久化。

Rope 实现持久化可以参考 Python 的引用计数机制。

当拷贝一个 Rope 实例时，如果没有更改数据，实际上不会进行真实的数据复制。只是增加了最初实例所管理数据的引用计数。

在进行更改操作时，仅修改需要更改的部分节点。

尽管功能十分强大， Rope 还是有很大的局限性。

性能，占用空间都是它的劣势。

最重要的一点是，为了实现某些功能往往要比正解的数据结构多带一个 log 量级的复杂度，而且有可能会遇到卡常的情况。

这种情况也不绝对，当使用 Rope 进行可持久化时，其它数据结构操作的时间复杂度能达到 log * log ，而 Rope 理论上则依然是 log ，这都是由于 O(1) 拷贝所带来的优势，这也使得在可持久化方面 Rope 勉强能和这些数据结构 46 开。

当然，这些劣势在 Rope 极其简单的使用方式下都不足挂齿，它真的是太好写了。

接下来讲一讲怎么使用 Rope 。

• Rope 的引用很方便， #include <ext/rope> 或者 #include<bits/extc++.h> 皆可。它的命名空间是 __gnu_cxx 。

• Rope 的声明可以参照 vector ，特殊的， __gnu_cxx::rope<char> 等价于 __gnu_cxx::crope 。

  __gnu_cxx::rope<int> rope;
  __gnu_cxx::rope<char> crope;
  

• Rope 的使用可以参照 vector 与 string ，常用的成员函数包括：

  • push_back(x)

  • insert(pos,x)

  • substr(pos,len)

  • erase(pos,len)

  • begin()

  • end()

  • size()

  • empty()

  • clear()

  这些大家都很熟悉了，具体用法也是你想的那样，这里不多做解释。当然了，还有很多其它的成员函数没有包括，可自行搜索。

  对了， Rope 可以正常的使用 std::cin 和 std::cout ， 你也可以像 string 那样用 + 号拼接两个 Rope 实例。

接下来就写点例题巩固一下吧。

P3369 【模板】普通平衡树

#include <bits/stdc++.h>

#include <ext/rope>

int main() {
    int n, inf = 1e9;
    std::cin >> n;
    __gnu_cxx::rope<int> rope;
    rope.push_back(-inf);
    rope.push_back(inf);

    auto lower_bound = [&](int u) -> int {
        return std::lower_bound(rope.begin(), rope.end(), u) - rope.begin();
    };

    auto upper_bound = [&](int u) -> int {
        return std::upper_bound(rope.begin(), rope.end(), u) - rope.begin();
    };

    while (n--) {
        int op, x;
        std::cin >> op >> x;

        if (op == 1) {
            int idx = lower_bound(x);
            rope.insert(idx, x);
        } else if (op == 2) {
            int idx = lower_bound(x);
            rope.erase(idx, 1);
        } else if (op == 3) {
            int idx = lower_bound(x);
            std::cout << idx << '\n';
        } else if (op == 4) {
            std::cout << rope[x] << '\n';
        } else if (op == 5) {
            int idx = lower_bound(x);
            std::cout << rope[idx - 1] << '\n';
        } else {
            int idx = upper_bound(x);
            std::cout << rope[idx] << '\n';
        }
    }

    return 0;
}

P3391 【模板】文艺平衡树

#include <bits/stdc++.h>

#include <ext/rope>

int main() {
    int n, m;
    std::cin >> n >> m;
    __gnu_cxx::rope<int> a, b;

    for (int i = 0; i < n; i++) {
        a.append(i + 1);
        b.append(n - i);
    }

    while (m--) {
        int l, r;
        std::cin >> l >> r;
        --l, --r;
        int len = r - l + 1;

        auto center = a.substr(l, len);
        a = a.substr(0, l) + b.substr(n - l - len, len) +
            a.substr(r + 1, n - (r + 1));
        b = b.substr(0, n - l - len) + center + b.substr(n - l, n - (n - l));
    }

    for (auto it : a) {
        std::cout << it << ' ';
    }

    return 0;
}

P6136 【模板】普通平衡树（数据加强版）

这道题使用 Rope 就通过不了。

23 个点只过了 9 个。

#include <bits/stdc++.h>

#include <ext/rope>

int main() {
    int n, m, inf = (1 << 30);
    std::cin >> n >> m;

    std::vector<int> a(n);

    for (auto &it : a) {
        std::cin >> it;
    }

    std::sort(a.begin(), a.end());

    __gnu_cxx::rope<int> t;
    t.push_back(-inf);
    for (auto it : a) {
        t.push_back(it);
    }
    t.push_back(inf);

    int res = 0, last = 0;

    auto find = [&](int u) -> int {
        return std::lower_bound(t.begin(), t.end(), u) - t.begin();
    };

    auto find_next = [&](int u) -> int {
        return std::upper_bound(t.begin(), t.end(), u) - t.begin();
    };

    while (m--) {
        int op, x;
        std::cin >> op >> x;

        x ^= last;

        if (op == 1) {
            int idx = find(x);
            t.insert(idx, x);
        } else if (op == 2) {
            int idx = find(x);
            t.erase(idx, 1);
        } else if (op == 3) {
            int idx = find(x);
            last = idx;
            res ^= idx;
        } else if (op == 4) {
            last = t[x];
            res ^= t[x];
        } else if (op == 5) {
            int idx = find(x);
            last = t[idx - 1];
            res ^= t[idx - 1];
        } else {
            int idx = find_next(x);
            last = t[idx];
            res ^= t[idx];
        }
    }

    std::cout << res << '\n';

    return 0;
}

P3835 【模板】可持久化平衡树

这题 25 个点， TLE 了两个点。可以看到，和正常写法相比还是过于取巧了。

不过至少过了大部分测试数据不是吗？

#include <bits/stdc++.h>

#include <ext/rope>

int main() {
    int n, inf = 2147483647;
    std::cin >> n;
    __gnu_cxx::rope<int> rope;
    std::vector<__gnu_cxx::rope<int>> backup;
    rope.push_back(-inf);
    rope.push_back(inf);
    backup.push_back(rope);

    auto lower_bound = [&](int u) -> int {
        return std::lower_bound(rope.begin(), rope.end(), u) - rope.begin();
    };

    auto upper_bound = [&](int u) -> int {
        return std::upper_bound(rope.begin(), rope.end(), u) - rope.begin();
    };

    while (n--) {
        int v, op, x;
        std::cin >> v >> op >> x;

        rope = backup[v];

        if (op == 1) {
            int idx = lower_bound(x);
            rope.insert(idx, x);
        } else if (op == 2) {
            int idx = lower_bound(x);
            if (x == rope[idx]) rope.erase(idx, 1);
        } else if (op == 3) {
            int idx = lower_bound(x);
            std::cout << idx << '\n';
        } else if (op == 4) {
            std::cout << rope[x] << '\n';
        } else if (op == 5) {
            int idx = lower_bound(x);
            std::cout << rope[idx - 1] << '\n';
        } else {
            int idx = upper_bound(x);
            std::cout << rope[idx] << '\n';
        }
        backup.push_back(rope);
    }

    return 0;
}

P3919 【模板】可持久化线段树 1（可持久化数组）

12 个点 TLE 了 4 个。

测试数据太狠了。

#include <bits/stdc++.h>

#include <ext/rope>

int main() {
    int n, m;
    std::cin >> n >> m;
    __gnu_cxx::rope<int> rope;
    std::vector<__gnu_cxx::rope<int>> backup;

    while (n--) {
        int x;
        std::cin >> x;
        rope.push_back(x);
    }

    backup.push_back(rope);

    while (m--) {
        int v, op, loc, x;
        std::cin >> v >> op >> loc;
        --loc;
        rope = backup[v];

        if (op == 1) {
            std::cin >> x;
            rope.replace(loc, x);
        } else {
            std::cout << rope[loc] << '\n';
        }

        backup.push_back(rope);
    }

    return 0;
}