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一概不支持……
| 函数 | 功能 |
| push_back(x) | 在末尾添加x |
| insert(pos,x) | 在pos插入x |
| erase(pos,x) | 从pos开始删除x个 |
| replace(pos,x) | 从pos开始换成x |
| substr(pos,x) | 提取pos开始x个 |
| at(x)/[x] |
访问第x个元素 |
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;
}
2025年1月19日 21:43
Hey there! I could have sworn I’ve been to this website before but after reading through some of the post I realized it’s new to me. Nonetheless, I’m definitely happy I found it and I’ll be book-marking and checking back frequently
2025年1月20日 15:22
Students pursuing higher studies in USA often feel overburdened with the assignment topics. It becomes tough for students to complete the paper work on time. The reason is that they are always running out of time because they are following a busy schedule with the daily life. Moreover, lack of precise skills of writing and exploring is also a bigger obstacle in their way. Yet, with our Assignment Help these obstacles can be passing over easily.
2025年1月20日 15:47
Because of the innovative progression of internet gaming in the previous few years, the craving to have the best PC for second life and other virtual game has been radically expanded among game sweethearts
2025年1月20日 16:06
notable put up i should instances this year! Thank you for informative post.
2025年1月20日 16:06
At the official Cash App help section, you will be able to determine almost all sorts of charges and fees while using the Cash App services. Apart from that, you will need to contact the Cash App support representatives who will help you to understand each and every thing about the same. So, whenever you come across any query regarding the same, you should go to the help section right now
2025年1月20日 16:47
Understanding and facilitating well-informed decision-making
2025年1月20日 16:48
We're not always present inattentive or agitated, take him to the doctor and ask:
2025年1月20日 17:13
I’m not positive the place for my mission.
2025年1月20日 17:45
Macular degeneration, which affects the center of your vision and can begin as early as age 50, is reaching crisis levels: It is the leading cause of blindness in America. More than ten million people have reduced vision due to the disease, with 200,000 new cases every year. If you've been diagnosed with macular degeneration, talk to an ophthalmologist and ask:
2025年1月20日 18:39
If you're interested in coding then you should make your career while learning web development courses in Delhi from one of the best web development training institute.
2025年1月20日 18:40
Nice post. I discover something very complicated on distinct blogs everyday. Most commonly it is stimulating to read content off their writers and use a specific thing from their store. I’d would rather apply certain with all the content on my own blog no matter whether you do not mind. Natually I’ll supply you with a link for your internet weblog. Many thanks sharing.
2025年1月20日 18:41
Excellent read. I just passed this onto a colleague who was doing some research on that. He actually bought me lunch as I found it for him! Therefore let me rephrase: Thanx for lunch!
2025年1月20日 18:41
Aneurysms can occur as a birth defect or may develop later in life. It's estimated that five percent of the population have some type of aneurysm in the brain; these could rupture at any time. If you have a severe headache accompanied by nausea, vomiting, or seizures or any other neurological symptoms, go to the ER or call 911 immediately.
2025年1月20日 18:41
I’m not positive the place you are getting your info, but great topic. I must spend a while finding out much more or figuring out more. Thank you for magnificent info I was in search of this information for my mission.
2025年1月20日 18:42
I\'m writing on this topic these days, but I have stopped writing because there is no reference material. Then I accidentally found your article. I can refer to a variety of materials, so I think the work I was preparing will work! Thank you for your efforts.
2025年1月20日 19:16
ZenCortex is a natural supplement that helps keep your brain and ears healthy. It uses special ingredients like Grape Seed and Green Tea to support clear thinking and good hearing. It\'s easy to take and made with plants, so it\'s safe and good for you!
2025年1月20日 19:17
Thanks i assume this is aontent material is actually well-researched. Thank you
2025年1月20日 19:19
Aneurysms can be successfully treated if they're caught in time. If you're experiencing horrible, recurrent headaches or even one episode of the single most painful headache you've ever had, see a doctor and ask:
2025年1月20日 19:20
If you've been tacklssionals for help.They will complete the difficult assignments for you.
2025年1月20日 19:22
I think this is one of the most important information for me. And i’m glad reading your article. But want to remark on some general things, The website style is wonderful, the articles is really great : D. Good job, cheers
2025年1月20日 19:24
I was surfing net and fortunately came across this site and found very interesting stuff here. Its really fun to read. I enjoyed a lot. Thanks for sharing this wonderful information
2025年1月20日 19:27
Excellent read. I just passed this onto a colleague who was doing some research on that. He actually bought me lunch as I found it for him! Therefore let me rephrase: Thanx for lunch!
2025年1月20日 19:28
Users of the Cash App shothe home screen of the cash app, they must select the banking menu. They can also seek assistance from the cash app service staff for guidance.