STL rope

rope的时间复杂度

查询复杂度是P(N½)，插入复杂度是P(N½)，空间复杂度是O(N)。

rope初始用法

初始的rope存放的类型是string。

1. insert(int pos,string &s,int n) 把字符串s中的前n位插入rope下标pos处。
2. append(string &s,int pos,int n)把字符串s中从下标pos开始的n个字符连接到rope的结尾
3. substr(int pos,int len)提取rope的从下标pos开始的len个字符
4. erase(int pos,int num)从rope的下标pos开始删除num个字符
5. copy(int pos,int len,string &s)从rope的下标pos开始的len个字符用字符串s代替，如果pos后的位数不够就补足
6. replace(int pos,string &x)从rope的下标pos开始替换成字符串x，x的长度为从pos开始的位数，如果pos后的位数不够就补足。所以这个不是少了一个参数的copy吗？

rope的常用用法

雾

rope存放的类型大多是int.

1. insert(int pos,int *s,int n) 把s中的前n位插入rope下标pos处。
2. append(int *s,int pos,int n)把字符串s中从下标pos开始的n个字符连接到rope的结尾
3. substr(int pos,int len)提取rope的从下标pos开始的len个数
4. erase(int pos,int num)从rope的下标pos开始删除num个数
5. copy(int pos,int len,int *s)从rope的下标pos开始的len个数用s代替，如果pos后的位数不够就补足
6. replace(int pos,int *x)从rope的下标pos开始替换成字符串x，x的长度为从pos开始的位数，如果pos后的位数不够就补足。所以这个不是少了一个参数的copy吗？

当然,它有size()

注意事项

使用时要加#include<ext/rope>

using namespace __gnu_cxx;

例题

给道例题

#include <ext/rope>
#include<bits/stdc++.h>
using namespace std;
using namespace __gnu_cxx;
rope<int> S;
void solve() {
    int n, q;
    cin >> n >> q;
    S.clear();
    for (int i = 1; i <= n; i++) {
        int t;
        cin >> t;
        S.push_back(t);
    }
    int ans = 0;
    while (q--) {
        int op, l, r, x;
        cin >> op;
        if (op == 1) {
            cin >> l >> r;
            S = S.substr(0, r) + S.substr(l - 1, n - r);
        } else {
            cin >> x;
            cout << S[x - 1] << endl;
        }
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

原文地址：http://www.cnblogs.com/zychh/p/16910243.html