引用站外地址
P4008 [NOI2003] 文本编辑器
洛谷

前言

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

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，光标位置不变n≥1n\geq1
Delete(n)\text{Delete}(n)Delete n删除光标后的 nn 个字符，光标位置不变，n≥1n \geq 1
Get(n)\text{Get}(n)Get n输出光标后的 nn 个字符，光标位置不变，n≥1n \geq 1
Prev()\text{Prev}()Prev光标前移一个字符
Next()\text{Next}()Next光标后移一个字符

你的任务是：

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

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

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

输入格式

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

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

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

行尾没有空格。

这里我们有如下假定：

  • MOVE 操作不超过 5000050000 个， INSERT 和 DELETE 操作的总个数不超过 40004000，PREV 和 NEXT 操作的总个数不超过 200000200000。

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

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

  • 输入文件没有错误。

对 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}) ，不过对于这道 1≤N≤2×1051\le N \le 2\times 10^5 的题勉强能过。

参考：

引用站外地址
块状链表
OI Wiki

Splay

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

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

参考：

引用站外地址
Splay 树
OI Wiki

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;
}