Ryan_<

Rope是类似块状链表的结构。把每个子字符串作为结点，串连为一个字符串，这样做，可以节省内存，避免了字符串构造时需要反复地构建：str = A+B+C, D= A+B, E= D+C, str= E。

String是“细线”，而Rope是“重绳”，用于解决巨型字符串的问题。

http://www.sgi.com/tech/stl/Rope.html

http://fanhq666.blog.163.com/blog/static/81943426201161095456671/

https://en.wikipedia.org/wiki/Rope_(data_structure)

首先声明：

rope原来属于SGI STL的一部分，不属于ISO C++标准库，但libstdc++-v3也包含了扩展，在<ext/rope>，__gnu_cxx命名空间中。

rope特性：

1、对涉及长字符串的连接与子串问题的处理很优秀。

字符串通过串联表示，故单个字符的修改实际上是两个子串的拼接操作，代价较大。

2、可以查询某个历史版本的字符串，即是可持久化的。所以大概rope的迭代器非常神奇。

3、空间上的优势，这大概是容器类型均具有的吧。

一个长度为10^6的字符串只需要不到1MB的空间！

甚至可以用一个rope来管理长达几百M的字符串却只占用十几个K的内存，所有的操作用时几乎和串的长度无关。

4、比vector还要慢，常数5~10倍。

rope资瓷的操作：

写一个rope<char> a，然后，把a当作一个字符串：
1.在log时间、空间内取a的一个子串
2.在log时间、空间内将两个串链接起来
也就是说，这是一个支持查找、插入、删除、剪切、复制的一个超级强大的数据结构。

zky:
由于rope的底层实现，insert，erase，get都是logn的
就是翻转不行，不是自己手写的打不了标记啊！！
怎么办？
答：同时维护一正一反两个rope,反转即交换两个子串
区间循环位移？简单，拆成多个子串连起来就好了
区间a变b b变c c变d …… z变a？ 呃……维护26个rope？
区间和？滚蛋，那是线段树的活
区间kth？sorry，与数值有关的操作rope一概不支持……

rope实现和应用：

像std::string一样，它本身就是一个类模板，已经提供了crope和wrope实例化版本供使用。

crope r(1000000, 'x');          // crope is rope<char>. wrope is rope<wchar_t>
                                // Builds a rope containing a million 'x's.
                                // Takes much less than a MB, since the
                                // different pieces are shared.
crope r2 = r + "abc" + r;       // concatenation; takes on the order of 100s
                                // of machine instructions; fast
crope r3 = r2.substr(1000000, 3);       // yields "abc"; fast.
crope r4 = r2.substr(1000000, 1000000); // also fast.
reverse(r2.mutable_begin(), r2.mutable_end());
                                // correct, but slow; may take a
                                // minute or more.

bzoj1269:[AHOI2006]文本编辑器editor

#include<bits/stdc++.h>
#include<ext/rope>//stl extend
#define F(i,s,t) for(int i=(s);i<=(t);i++)
using namespace std; 
using namespace __gnu_cxx;
typedef long long LL;
inline LL read()
{
    LL x=0;char ch=getchar();
    while(ch>'9'||ch<'0')ch=getchar();
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
const int N=(int)2e6;
int m,len,now;
char opt[10],s[N],revs[N];
rope<char> a,b,tmp; 
int main()
{
	m=read();int x;
	while(m--){
		scanf("%s",opt);
		switch(opt[0]){
			case 'M':now=read();break;
			case 'P':now--;break;
			case 'N':now++;break;
			case 'G':printf("%c\n",a[now]);break;
			case 'I':
				x=read();len=a.length();//**得到长度 
				F(i,0,x-1){//读入含空格的字符串 
					s[i]=getchar();
					while(s[i]=='\n') s[i]=getchar();
					revs[x-1-i]=s[i];
				}
				revs[x]=s[x]=0;//否则会MLE! 
				a.insert(now,s);//**在pos插入x
				b.insert(len-now,revs);
				break;
			case 'D':
				x=read();len=a.length();
				a.erase(now,x);//**从pos开始删除x个
				b.erase(len-now-x,x);
				break;  
			case 'R':
				x=read();len=a.length();
				tmp=a.substr(now,x);//**提取pos开始x个
				a=a.substr(0,now)+b.substr(len-now-x,x)+a.substr(now+x,len-now-x); 
				b=b.substr(0,len-now-x)+tmp+b.substr(len-now,now);  
				break;  
			}
		}
	return 0;
}

NOI2002 Editor

#include<iostream>
#include<cstdio>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
crope list;
int t,now;
char ch[3000005];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int main()
{
    t=read();
    char s[10];int x;
    while(t--)
    {
        scanf("%s",s);
        switch(s[0])
        {
        case 'M':now=read();break;
        case 'P':now--;break;
        case 'N':now++;break;
        case 'I':
            x=read();
            for(int i=0;i<x;i++)
            {
                ch[i]=getchar();
                while(ch[i]=='\n')ch[i]=getchar();
            }
            ch[x]=0;
            list.insert(now,ch);
            break;
        case 'D':x=read();list.erase(now,x);break;
        case 'G':x=read();list.copy(now,x,ch);ch[x]=0;puts(ch);
        }
    }
    return 0;
}