rope

基本操作

头文件

#include <ext/rope>

命名空间

using namespace __gnu_cxx;

定义

rope<char> c; //等价于crope c;
rope<int> t;
roep<Type> r;

运算符 “+”：可以连接两个rope

(rope 或 crope)
运算符 “<< ”和“ >> ”：可由输入输出流读入或输出。

cout << c << endl;

• c.length()/c.size() 返回长度/大小

• push_front(x); //在首部添加x

• push_back(x); //在末尾添加x

• c.insert(pos, x); //在pos插入x，x可以是一个元素也可以是一个数组

• c.erase(pos, x);//从pos开始删除x个

• c.copy(pos, len, x); //把c[pos~(pos+x-1)]复制到x

• c.replace(pos, x); //从pos开始换成x

• c.substr(pos, x); //返回一个rope类型，而且等于c[pos~(pos+x-1)]，且两者互不相干。

• c.at(x)/c[x]; //访问第x个元素

(O(1))拷贝历史版本

指针

rope<Type> *a, *b;
a = new rope<Type>;
b = new rope<Type> (*a);

非指针

rope<Type> a, b;
a = b;

应用

Editor

#include <iostream>
#include <cstdio>
#include <cstring>
#include <ext/rope>

using namespace std;
using namespace __gnu_cxx;

const int N = 1 << 22;

char ch[N];
crope text;

int main() {
    int t, p = 0;
    scanf("%d", &t);
    while (t--) {
        char op[20];
        scanf("%s", op);
        if (op[0] == 'M') scanf("%d", &p);
        else if (op[0] == 'P') --p;
        else if (op[0] == 'N') ++p;
        else if (op[0] == 'I') {
            int n;
            scanf("%d", &n);
            for (int i = 0; i < n; ++i) {
                do scanf("%c", ch + i);
                while (ch[i] < 31 || 126 < ch[i]);
            }
            ch[n] = 0;
            text.insert(p, ch);
        } else if (op[0] == 'D') {
            int n;
            scanf("%d", &n);
            text.erase(p, n);
        } else {
            int n;
            scanf("%d", &n);
            text.copy(p, n, ch);
            ch[n] = 0;
            puts(ch);
        }
    }
    return 0;
}

文本编辑器

#include <iostream>
#include <cstdio>
#include <cstring>
#include <ext/rope>

using namespace std;
using namespace __gnu_cxx;

const int N = 1 << 22;

char ch[N];
crope tt, rt, tmp;

int main() {
    int t, p = 0;
    scanf("%d", &t);
    while (t--) {
        char op[20];
        scanf("%s", op);
        if (op[0] == 'M') scanf("%d", &p);
        else if (op[0] == 'P') --p;
        else if (op[0] == 'N') ++p;
        else if (op[0] == 'I') {
            int n;
            scanf("%d", &n);
            for (int i = 0; i < n; ++i) {
                do scanf("%c", ch + i);
                while (ch[i] < 32 || 126 < ch[i]);
            }
            ch[n] = 0;
            int len = tt.length();
            tt.insert(p, ch);
            reverse(ch, ch + n);
            rt.insert(len - p, ch);
        } else if (op[0] == 'D') {
            int n, len = tt.length();
            scanf("%d", &n);
            tt.erase(p, n);
            rt.erase(len - p - n, n);
        } else if (op[0] == 'R') {
            int n, len = tt.length();
            scanf("%d", &n);
            tmp = tt.substr(p, n);
            tt = tt.substr(0, p) + rt.substr(len - p - n, n) + tt.substr(p + n, len - p - n);
            rt = rt.substr(0, len - p - n) + tmp + rt.substr(len - p, p);
        } else if (op[0] == 'G') printf("%c
", tt[p]);
    }
    return 0;
}

文艺平衡树

#include <iostream>
#include <cstdio>
#include <cstring>
#include <ext/rope>

using namespace std;
using namespace __gnu_cxx;

int n, m;
rope<int> s, t, tmp;

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        s.push_back(i);
    for (int i = n; i; --i)
        t.push_back(i);
    while (m--) {
        int l, r;
        scanf("%d%d", &l, &r);
        int len = r - l + 1;
        tmp = s.substr(l - 1, len);
        s = s.substr(0, l - 1) + t.substr(n - r, len) + s.substr(r, n - r);
        t = t.substr(0, n - r) + tmp + t.substr(n - l + 1, l);
    }
    for (int i = 0; i < n; ++i)
        printf("%d ", s[i]);
    puts("");
    return 0;
}