前言

某普及组蒟蒻居然做紫题?这是人性的扭曲还是道德的沦丧?

STL大水模拟,逃(

题面

点击查看题面

[NOI2003] 文本编辑器

题目描述

很久很久以前,DOS3.xDOS3.x 的程序员们开始对 EDLINEDLIN 感到厌倦。于是,人们开始纷纷改用自己写的文本编辑器⋯⋯

多年之后,出于偶然的机会,小明找到了当时的一个编辑软件。进行了一些简单的测试后,小明惊奇地发现:那个软件每秒能够进行上万次编辑操作(当然,你不能手工进行这样的测试) !于是,小明废寝忘食地想做一个同样的东西出来。你能帮助他吗?

为了明确目标,小明对“文本编辑器”做了一个抽象的定义:

文本:由 00 个或多个 ASCII 码在闭区间 [3232, 126126] 内的字符构成的序列。

光标:在一段文本中用于指示位置的标记,可以位于文本首部,文本尾部或文本的某两个字符之间。

文本编辑器:由一段文本和该文本中的一个光标组成的,支持如下操作的数据结构。如果这段文本为空,我们就说这个文本编辑器是空的。

操作名称 输入文件中的格式 功能
Move(k)\text{Move}(k) Move k 将光标移动到第 kk 个字符之后,如果 k=0k=0,将光标移到文本开头
Insert(n,s)\text{Insert}(n,s) Insert n s 在光标处插入长度为 nn 的字符串 ss,光标位置不变n1n\geq1
Delete(n)\text{Delete}(n) Delete n 删除光标后的 nn 个字符,光标位置不变,n1n \geq 1
Get(n)\text{Get}(n) Get n 输出光标后的 nn 个字符,光标位置不变,n1n \geq 1
Prev()\text{Prev}() Prev 光标前移一个字符
Next()\text{Next}() Next 光标后移一个字符

你的任务是:

  • 建立一个空的文本编辑器。

  • 从输入文件中读入一些操作并执行。

  • 对所有执行过的 GET 操作,将指定的内容写入输出文件。

输入格式

输入文件 editor.in 的第一行是指令条数 tt,以下是需要执行的 tt 个操作。其中:

为了使输入文件便于阅读, Insert 操作的字符串中可能会插入一些回车符, 请忽略掉它们(如果难以理解这句话,可以参照样例) 。

除了回车符之外,输入文件的所有字符的 ASCII 码都在闭区间 [3232, 126126] 内。且

行尾没有空格。

这里我们有如下假定:

  • MOVE 操作不超过 5000050000 个, INSERTDELETE 操作的总个数不超过 40004000PREVNEXT 操作的总个数不超过 200000200000

  • 所有 INSERT 插入的字符数之和不超过 2M2M1M=1024×10241M=1024\times 1024 字节) ,正确的输出文件长度不超过 3M3M 字节。

  • DELETE 操作和 GET 操作执行时光标后必然有足够的字符。 MOVEPREVNEXT 操作必然不会试图把光标移动到非法位置。

  • 输入文件没有错误。

对 C++ 选手的提示:经测试,最大的测试数据使用 fstream 进行输入有可能会比使用 stdio 慢约 11 秒。

输出格式

输出文件 editor.out 的每行依次对应输入文件中每条 Get 指令的输出。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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

样例输出 #1

1
2
.\/.
abcde^_^f.\/.ghijklmno

正常做题思想

块状链表

块状链表本身的原理是:将一个链表分割成 N\sqrt{N} 个长为 N\sqrt{N} 的块,并为每一个块创建一个数组索引,每次访问时先找到元素对应的块,再在每一个块中朴素查找。

这样时间复杂度为 O(NN)O(N \sqrt{N}) ,不过对于这道 1N2×1051\le N \le 2\times 10^5 的题勉强能过。

参考:

Splay

不过问题是:链表不断更新,如何维护每一个块,使每个块保持 N\sqrt{N} 的长度呢?

这确实很复杂,考虑的细节很多,所以还有一种叫做Splay的树来维护(但本蒟蒻不会 qwq

参考:

STL大水法

介绍

这道题用高级数据结构虽然比较麻烦(如上),不过GCC给我们提供了一个利器:ext/rope

这是内置于 gcc 编译器的 ext 文件夹内的头文件中定义的数据结构,并非ISO C++,当然使用的命名空间也有所不同,并且有两条下划线:

1
using namespace __gnu_cxx;

不过大家不用担心,按照€€£在2021年发布的公告的说法,明确支持了双下划线开头的库函数可以在竞赛中使用!!!(CCF你变了好多,当年你还不准用STL呢!)

名义上这是一种块状链表,本来是设计来存储字符串,当然实际上是使用可持久化平衡树实现的,所以复杂度实际上是O(n log n)O(n\ log\ n),更加优秀。

用法

使用以下方式引入它:

1
2
#include <ext/rope>
using namespace __gnu_cxx; //因为这是g++内置非标库函数

初始化一个rope:

1
2
3
4
rope<int> rp; //创建一个int类型的rope,这常被用来水主席树(
rope<pair<string,int>> rp2; //创建一个存储了pair<string,int>的rope
crope rp3; //这等价于下面的:
rope<char> rp3;

插入元素:

1
2
3
4
5
6
7
8
9
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 等手打快读来卡常。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
//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;
}