前往以下网站，不保证安全性哦喵~P4008 [NOI2003] 文本编辑器洛谷
某普及组蒟蒻居然做紫题？这是人性的扭曲还是道德的沦丧？
STL大水模拟，逃（
很久很久以前，$DOS3.x$ 的程序员们开始对 $EDLIN$ 感到厌倦。于是，人们开始纷纷改用自己写的文本编辑器⋯⋯
多年之后，出于偶然的机会，小明找到了当时的一个编辑软件。进行了一些简单的测试后，小明惊奇地发现：那个软件每秒能够进行上万次编辑操作（当然，你不能手工进行这样的测试） ！于是，小明废寝忘食地想做一个同样的东西出来。你能帮助他吗？
为了明确目标，小明对“文本编辑器”做了一个抽象的定义:
文本：由 $0$ 个或多个 ASCII 码在闭区间 [$32$, $126$] 内的字符构成的序列。
光标：在一段文本中用于指示位置的标记，可以位于文本首部，文本尾部或文本的某两个字符之间。
文本编辑器：由一段文本和该文本中的一个光标组成的，支持如下操作的数据结构。如果这段文本为空，我们就说这个文本编辑器是空的。
| 操作名称 | 输入文件中的格式 | 功能 |
|---|---|---|
| $\text{Move}(k)$ | Move k | 将光标移动到第 $k$ 个字符之后，如果 $k=0$，将光标移到文本开头 |
| $\text{Insert}(n,s)$ | Insert n s | 在光标处插入长度为 $n$ 的字符串 $s$，光标位置不变$n\geq1$ |
| $\text{Delete}(n)$ | Delete n | 删除光标后的 $n$ 个字符，光标位置不变，$n \geq 1$ |
| $\text{Get}(n)$ | Get n | 输出光标后的 $n$ 个字符，光标位置不变，$n \geq 1$ |
| $\text{Prev}()$ | Prev | 光标前移一个字符 |
| $\text{Next}()$ | Next | 光标后移一个字符 |
你的任务是：
建立一个空的文本编辑器。
从输入文件中读入一些操作并执行。
对所有执行过的 GET 操作，将指定的内容写入输出文件。
输入文件 editor.in 的第一行是指令条数 $t$，以下是需要执行的 $t$ 个操作。其中：
为了使输入文件便于阅读， Insert 操作的字符串中可能会插入一些回车符， 请忽略掉它们（如果难以理解这句话，可以参照样例） 。
除了回车符之外，输入文件的所有字符的 ASCII 码都在闭区间 [$32$, $126$] 内。且
行尾没有空格。
这里我们有如下假定：
MOVE 操作不超过 $50000$ 个， INSERT 和 DELETE 操作的总个数不超过 $4000$，PREV 和 NEXT 操作的总个数不超过 $200000$。
所有 INSERT 插入的字符数之和不超过 $2M$（$1M=1024\times 1024$ 字节） ，正确的输出文件长度不超过 $3M$ 字节。
DELETE 操作和 GET 操作执行时光标后必然有足够的字符。 MOVE 、 PREV 、 NEXT 操作必然不会试图把光标移动到非法位置。
输入文件没有错误。
对 C++ 选手的提示：经测试，最大的测试数据使用 fstream 进行输入有可能会比使用 stdio 慢约 $1$ 秒。
输出文件 editor.out 的每行依次对应输入文件中每条 Get 指令的输出。
15
Insert 26
abcdefghijklmnop
qrstuv wxy
Move 15
Delete 11
Move 5
Insert 1
^
Next
Insert 1
_
Next
Next
Insert 4
.\/.
Get 4
Prev
Insert 1
^
Move 0
Get 22.\/.
abcde^_^f.\/.ghijklmno块状链表本身的原理是：将一个链表分割成 $\sqrt{N}$ 个长为 $\sqrt{N}$ 的块，并为每一个块创建一个数组索引，每次访问时先找到元素对应的块，再在每一个块中朴素查找。
这样时间复杂度为 $O(N \sqrt{N})$ ，不过对于这道 $1\le N \le 2\times 10^5$ 的题勉强能过。
参考：
不过问题是：链表不断更新，如何维护每一个块，使每个块保持 $\sqrt{N}$ 的长度呢？
这确实很复杂，考虑的细节很多，所以还有一种叫做Splay的树来维护（但本蒟蒻不会 qwq
参考：
前往以下网站，不保证安全性哦喵~Splay 树OI Wiki
这道题用高级数据结构虽然比较麻烦（如上），不过GCC给我们提供了一个利器：ext/rope。
这是内置于 gcc 编译器的 ext 文件夹内的头文件中定义的数据结构，并非ISO C++，当然使用的命名空间也有所不同，并且有两条下划线：
using namespace __gnu_cxx;不过大家不用担心，按照€€￡在2021年发布的公告的说法，明确支持了双下划线开头的库函数可以在竞赛中使用！！！（CCF你变了好多，当年你还不准用STL呢！）
名义上这是一种块状链表，本来是设计来存储字符串，当然实际上是使用可持久化平衡树实现的，所以复杂度实际上是$O(n\ log\ n)$，更加优秀。
使用以下方式引入它：
#include <ext/rope>
using namespace __gnu_cxx; //因为这是g++内置非标库函数初始化一个rope：
rope<int> rp; //创建一个int类型的rope，这常被用来水主席树（
rope<pair<string,int>> rp2; //创建一个存储了pair<string,int>的rope
crope rp3; //这等价于下面的：
rope<char> rp3;插入元素：
crope test;
test.push_back(x); //在末尾添加x
test.insert(pos,x); //在pos插入x
test.erase(pos,x); //从pos开始删除x个
test.copy(pos,len,x); //从pos开始到pos+len为止用x代替
test.replace(pos,x); //从pos开始换成x元素
test.substr(pos,x); //提取pos开始x个元素
test.at(x); //访问第x个元素，这等价于下面的：
tast[x];这就是 rope 的简单水法了。
现在我们就可以把 crope 存储的文本当作 string 一样对待来打模拟了，用pos表示光标位置，按照题目指引模拟做题即可。
注意读入不能用 cin cout，建议关闭流同步（注意这时不要使用 string ）或使用 scanf printf，也可以使用 getchar putchar puts 等手打快读来卡常。
//QwQ
#include <bits/stdc++.h>
#include <ext/rope>
using namespace __gnu_cxx;
using namespace std;
crope R; //存储文本
char cmd[24],s[19198101]; //cmd读入命令，s读入文字
int t,pos,n; //pos存光标位置
inline int readint(){ //快读，读int
char c;
while(!isdigit(c=getchar()));
int k=c-48;
while(isdigit(c=getchar()))
k=(k<<1)+(k<<3)+c-48;
return k;
}
inline void reads(char *s,int len){ //快读，读char*
s[len]='\0';
len--;
for(int i=0;i<=len;i++){
s[i]='\0';
while(s[i]<32||126<s[i]) s[i]=getchar();
}
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%s",&cmd);
switch(cmd[0]){ //不同命令
case 'M': //Move 移动光标
pos=readint();
break;
case 'I':{ //Insert 插入文本，注意作用域，加大括号
int len=readint();
reads(s,len);
R.insert(pos,s);
break;
}
case 'D': //Delete 删除文本
n=readint();
R.erase(pos,n);
break;
case 'G': //Get 读取文本
n=readint()-1;
for(int i=pos;i<=pos+n;i++)
putchar(R[i]);
printf("\n");
break;
case 'P': //Prev 向前移动光标
pos--;
break;
case 'N': //Next 向后移动光标
pos++;
break;
}
}
return 0;
}此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。