\STL大法好/

正规解法块状链表，这里采取的是黑科技解法。

\(rope\)是扩展\(STL\)库中的一个数据结构——可持久化平衡树,相比较\(set\)，它更适合区间插入和删除。这里用来解此题，就显得十分傻瓜容易了。

(资料图片)

头文件：#include

命名空间：using namespace __gnu_cxx;

基本操作：

insert(pos, s)将字符串s插入pos位置

erase(pos, num)从pos开始删除num个字符

copy(pos, len, s)从pos开始len个字符用s代替

substr(pos, len)提取pos开始的len个字符

at(x)访问第x个元素

几乎跟题目一模一样！

更开心的是，\(rope\)在\(NOI\)中是允许使用的（\(hooray\)）！

于是代码就十分简单了：

#include #include using namespace __gnu_cxx;using namespace std;rope  editor;char ch;string oper;int pos, n, rela;int main(){cin.tie(0);cout.tie(0);scanf("%d", &n);while(n--){    cin >> oper;    scanf("%d", &rela);    if(oper =="Insert"){    int pos1 = pos;while(rela){ch = getchar();if((int)ch >= 32 && (int)ch <= 126){    editor.insert(pos1, ch);    rela--;    pos1++;}}        }                else if(oper =="Move"){        pos = rela;        }                else if(oper =="Next"){            pos++;        }                else if(oper =="Prev"){        pos--;        }                else if(oper =="Get"){        cout << editor.substr(pos, rela) << endl;        }                else if(oper =="Delete"){        editor.erase(pos, rela);        }}return 0;}

\(rope\) 的可持久化

一般，我们可以利用 \(rope\) 底层可持久化的机制，进行 \(O(1)\) 回退。也就是我们只需要回退根节点的版本，我们就可以很顺利地访问当时的所有节点了。故回退复杂度为\(O(1)\)可持久化 \(rope\) 的初始化：

rope*ver[100];ver[0]=new rope();

可持久化 \(rope\) 建立新版本和回退旧版本：

ver[i]=new rope(*ver[i-1]);//从版本 (i-1) 建立新版本 iver[i]=ver[i-1]//版本 i 回退为版本 (i-1)

双倍经验 P4567 【AHOI2006】 文本编辑器

此题是上题的升级版，因为要实现rotate操作，所以存储两个rope，一正一反。

代码基本相同，略。