时间限制： 3.0 秒

空间限制： 2048 MB

题目背景

自从被安利了版本控制软件 Git，顿顿沉迷其中无法自拔。恰好最近学习了文件系统的一些知识，于是顿顿打算在办签证的途中实现一个类似于 Git 的特殊“文件系统” GeetFS。

题目描述

基本布局

普通的文件系统使用存储设备保存用户文件，

但是 GeetFS 不是一个普通的文件系统。

——顿顿

GeetFS 是一个基于内存的文件系统，其使用内存中的结构来保存和管理用户的文件数据。图 1 展示了 GeetFS 的工作流程和 GeetFS 保存数据的基本方式。在使用 GeetFS 时，用户发送请求给 GeetFS。GeetFS 会解析用户的请求，在内存数据结构中进行操作，完成用户请求。

GeetFS 中的一些基本概念

• 文件：与普通文件系统中的文件概念相同，GeetFS 中的文件可以保存数据。GeetFS 中的文件支持读取、写入、删除。写入一个不存在（或此前已被删除）的文件会自动创建该文件；
• 文件名：每个文件拥有一个文件名，为一个长度不超过 128 的字符串。文件名的内容仅包含大小写英文字母和数字（A-Za-z0-9）。顿顿认为 GeetFS 的用户都非常善良，所以他们能够保证每个 GeetFS 命令中的文件名均满足上述规定，GeetFS 在实现的时候无需进行检查。如图 1 中的 file1 表示一个名为 file1 的文件。
• 暗文件：为了表示文件的删除，GeetFS 中引入了暗文件的概念。对于一个名为 filename 的文件，其暗文件名称为 -filename（即在文件名前增加了一个负号 ‐）。由于在用户创建的文件名中不允许出现 ‐，暗文件的文件名与普通文件的文件名并不会混淆。暗文件的文件大小为 0，其中不可保存数据。其仅表示名为 filename 的文件被删除。一个文件与其暗文件不应同时出现在同一个提交中，也不应同时出现在暂存区中（关于提交和暂存区的概念请看下面两条）。如图 1 中的 ‐file2 为一个暗文件，表示对文件 file2 的删除。
• 暂存区：用户所有的修改，包括文件写入、删除等，在未提交时，均保存在暂存区（即图 1 中的 uncommitted 结构，包括虚线椭圆及其右侧的文件）。其中文件的写入（包括创建）以文件的形式保存，而文件的删除以暗文件的形式保存。
• 提交：与在 Git 中类似，一个提交表示 GeetFS 的一个历史状态。一般来说，提交由 commit 命令创建，GeetFS 将当前暂存区中的所有修改保存下来，并赋予一个唯一的提交名，成为一个提交。提交名的命名要求与文件名相同，且无需进行格式检查。除了 commit 命令外，用户还可以通过 merge 命令创建一个提交。通过 merge 命令创建的提交将两个现有提交进行合并。提交的创建在后文中有具体描述。除了 GeetFS 中的第一个提交不存在父提交之外，其余每个提交拥有一个父提交（由 commit 命令创建）或者两个父提交（由 merge 命令创建）。如图 1 中的 cmt1 表示一个名为 cmt1 的提交。
• HEAD：与 Git 中类似，HEAD 表示当前的头部，指向头部提交。用户当前能够访问哪些文件，以及文件的内容，取决于当前缓存区中的内容以及当前头部所指向的提交。
• GeetFS 命令：用户使用 GeetFS 命令对 GeetFS 的内容进行操作。命令只能通过标准输入传递给 GeetFS，除了write 命令占据两行之外，其他 GeetFS 均只占一行（即以换行符结尾）。

GeetFS 的存储结构

GeetFS 中保存了一个头部，一个暂存区结构，和若干个提交结构。

• 头部（HEAD）：GeetFS 中有且仅有一个头部，为指向当前头部提交的一个指针或者引用，当 GeetFS 中不存在任何提交时，头部为空。
• 暂存区结构（uncommitted）：GeetFS 中有且仅有一个暂存区结构。暂存区结构中包含了所有还未提交的修改。在此结构中，应该保存所有被修改（包括创建）文件的名称、大小和内容。对于删除的文件，该结构中应当保存对应的暗文件的信息。注意暗文件的大小为 0，不保存数据，因此只有暗文件的文件名是有意义的信息。
• 提交结构：GeetFS 中可以有零个或者多个提交结构，保存在元数据结构之中。暂存区结构中的内容在提交后，变为提交结构。一旦生成，提交结构中的内容是不可修改的。

初始状态

一个刚刚被创建出来的 GeetFS 文件系统只包括一个空头部和一个空的暂存区结构（即其中没有任何文件或暗文件）。

基本操作

普通的文件系统使用目录组织文件，

但是 GeetFS 不是一个普通的文件系统。

——顿顿

作为一个“与 (zhu) 众 (yao) 不 (shi) 同 (lan)”的文件系统，GeetFS 只支持对文件的操作，并不支持目录（文件夹），同时 GeekFS 支持的文件操作只有三个：写入、读取和删除。这三个操作均依赖于文件的查找。

文件的查找

查找一个文件 X 的流程如图 2 所示，具体规则如下：

1. 如果暂存区中能够查找到 X 文件，则找到了该文件；
2. 如果暂存区中不存在 X 文件，但是存在其暗文件 ‐X，则表示目标文件被删除，返回文件已被删除；
3. 如果在暂存区中，既不存在 X 文件，也不存在其暗文件，则在暂存区中无法确定是否存在该文件，需继续查找头部所指向的提交。如果头部为空，则文件不存在；
4. 在一个提交中查找文件的方法与在暂存区中查找的方法相同，即先后检查目标文件和其暗文件。如果该提交中依然无法确定是否存在该文件，则继续查找该提交的父提交，直至能够确定目标文件的存在性，或父提交不存在，则该文件不存在。对于具有两个父提交的提交，其查找方法在后文 merge 命令中给出。

写入命令

共包括两行输入，其中第一行格式为 write <filename> <offset> <len>（其中尖括号表示参数，下同），表示向文件 <filename> 中写入数据，写入的数据长度为 <len> 个字节，写入的开始位置为文件的 <offset> 位置（注意，在文件的位置 0 写入 1 个字符，写入的是文件的第 1 个字符）。如果 <offset> 的位置超出了该文件的大小，则从文件当前末尾到 <offset> 之间的区域使用 ASCII 字符点 . 进行填充。

在此行命令之后的一行，用户会输入 <len> 个字节作为文件内容，（注意结尾会有一个换行符 \n，不算做文件内容）。用户输入的内容中不包含换行字符，但是可能包含空格。

在执行写入命令时，GeetFS 首先按照前述方法查找该文件，并根据不同情况进行不同操作：

1. 如果在暂存区中该文件被找到，则直接进行写入操作；
2. 如果在某个提交中找到了该文件，则先将找到的文件拷贝到暂存区中（即在暂存区中创建该文件，并将找到的文件的内容拷贝到新文件中），再在暂存区中的文件中进行写入操作；
3. 如果查找结果为文件被删除，如果是在暂存区中被删除，则删除暂存区中对应的暗文件，并在暂存区中创建该文件后进行写入操作；
4. 如果是在某个提交中被删除，则在暂存区中创建该文件后进行写入操作；
5. 如果该文件不存在，则在暂存区中创建该文件，并进行写入操作。

写入命令不产生输出。

读取命令

共占一行，格式为 read <filename> <offset> <len>，表示从文件 <filename> 的 <offset> 位置开始读取此后的 <len> 个字节。对于超出文件当前大小的部分，每个超出的字节以一个 ASCII 字符点 . 替代。

在执行时，GeetFS 首先按前述方法查找该文件，如果能找到文件，则输出文件中对应的内容；如果文件不存在或者文件被删除，则输出 <len> 个 ASCII 字符点 .。文件读取命令的输出共占一行，因此在文件内容后应有换行 \n 字符，格式也可以参考样例。

删除命令

占一行，格式为 unlink <filename>，表示删除名为 <filename> 的文件。

如果 GeetFS 中无法找到该文件或该文件被删除，则什么都不做。如果能够找到该文件，则在暂存区中添加该文件的暗文件。如果目标文件是在暂存区中被找到的，则还需要从暂存区中删除目标文件，只保留其暗文件。

删除命令不产生输出。

注意，删除操作并不能抵消文件创建操作的效果。在文件 X 不存在的情况下，用户可以首先创建文件 X，之后将文件 X 删除。在删除后，暂存区中会存有一个 X 的暗文件 ‐X，与文件 X 被创建前的状态不同。

列举命令

占一行，格式为 ls，输出在当前的暂存区和当前的头部状态下，用户能够读到的文件（即可以查找到的文件，不包括暗文件）个数，以及其中按字典序排列，名字最小的文件名和名字最大的文件名。文件个数和两个文件名之间以一个空格隔开，共占一行。如果用户能读到的文件数为 0，则只需输出数字 0，占一行，无需给出文件名。列举命令的输出共占一行，因此在列举内容之后应有换行 \n 字符，具体可以参考样例。

高级操作

普通的文件系统仅仅是一个文件系统，

但是 GeetFS 不是一个普通的文件系统。

——顿顿

作为一个有 Git 情节的文件系统，GeetFS 当然不仅仅支持标准的文件系统接口。其还支持一系列与 Git 操作相似的高级命令。

提交命令

占一行，格式为 commit <cmtname>。

commit 命令将暂存区中的修改进行提交，其接受一个字符串类型参数 <cmtname>，为新提交的名称。

在进行提交时，GeetFS 将当前的暂存区 uncommitted 重命名为给定的提交名称，并更新元数据信息。新的提交 <cmtname> 的父提交为此时头部所指向的提交。如果此时头部为空，则新提交没有父提交。此后，GeetFS 将更新头部，让其指向刚刚创建的新提交 <cmtname>。最后，GeetFS 还会创建一个新的空暂存区，用于保存此后的修改。

注意，如果在提交时暂存区为空，或名为 <cmtname> 的提交已经存在，则该命令执行失败，GeetFS 中不产生任何修改。提交命令不产生任何输出。

切换命令

占一行，格式为 checkout <cmtname>。

checkout 接受一个参数，为提交名 <cmtname>。该命令将当前的头部指向 <cmtname>。在支持该命令之后，提交之间的关系可能会“分叉”。

checkout 命令不一定会成功。若在进行 checkout 时，暂存区不为空，或者名为 <cmtname> 的提交不存在，则 checkout 命令执行失败，GeetFS 中不应产生任何修改。

合并命令

占一行，格式为 merge <mergee> <cmtname>。

merge 命令接受两个参数，分别为需要合并的提交名 <mergee> 和新提交的名字 <cmtname>。假设此时头部指向的提交为 headcmt，该命令将 <mergee> 中的内容合并到提交 headcmt 之上。具体来说，GeetFS 会创建一个新的提交，名为 <cmtname>，其两个父提交为 headcmt 和 mergee。

由 merge 命令创建的提交中不包含任何文件和数据，只记录了两个父提交，表示这两个父提交的内容在逻辑上进行了合并。

注意，如果在进行 merge 时满足以下任何一个条件，则 merge 执行失败，GeetFS 中不产生任何修改：

1. 暂存区不为空；
2. <mergee> 与 headcmt 为同一个提交；
3. 名为 <mergee> 的提交不存在。

支持 merge 命令会影响文件查找的规则：在支持 merge 命令后，一个提交 cmt 可以有两个不同的父提交 cmt.parent1 和 cmt.parent2。在进行文件查找时，若在 cmt 中无法确定目标文件是否存在，则 GeetFS 需要通过 cmt.parent1 和 cmt.parent2 两个父提交分别进行文件查找。

1. 若通过两个父提交均无法找到目标文件或其暗文件，则表示要查找的文件不存在；
2. 若仅能通过其中一个父提交找到该目标文件或其暗文件，则以此找到的文件作为文件查找的结果；
3. 若通过两个父提交均能找到该目标文件或其暗文件，则根据所找到的两个文件的所在提交的创建时间进行选择，取创建时间最近（最大）的文件作为文件查找的结果。如果所找到的两个文件为同一个文件（即在同一个提交中），则以此文件作为文件查找的结果。

输入格式

从标准输入读入数据。

输入的第一行为一个数字 $n$，表示该测试中的命令总个数。

从第二行开始，标准输入共包含 $n$ 个命令。

• 每个写入命令 write 占两行，其中第一行为写入命令以 及其参数，第二行为需要写入的文件内容。文件内容中不会包含换行字符，但是可能会包含空格。
• 其他每个命令占一行，具体格式在前文已经给出。

命令均符合相应格式，文件名和提交名均符合规范，读写命令中的长度均大于 0，因此无需对命令格式进行错误处理。

输出格式

输出到标准输出。

根据每个命令的要求进行相应输出。

10
write file1 5 2
78
write file2 7 4
abcd
read file1 0 10
ls
read file2 4 10
unlink file2
ls
read file2 3 4
write file2 1 2
12
read file2 0 4

.....78...
2 file1 file2
...abcd...
1 file1 file1
....
.12.

样例 1 解释

此样例为简单的文件读写测试。

22
write file1 3 2
ab
commit cmt1
write file2 2 4
cdef
read file1 0 10
ls
unlink file1
commit cmt2
ls
checkout cmt1
read file1 0 10
write file1 6 2
gh
write file3 2 3
ijk
commit cmt3
ls
checkout cmt2
ls
merge cmt3 cmt4
ls
read file3 0 10
checkout cmt3
write file3 5 3
lmn
read file3 0 10

...ab.....
2 file1 file2
1 file2 file2
...ab.....
2 file1 file3
1 file2 file2
3 file1 file3
..ijk.....
..ijklmn..

样例 2 解释

此样例中的提交和内容关系如图 3 所示。

输出的第 1 行，对应输入第 7 行的 read 命令，其读取到了输入第 2 行中写入的数据；

输出的第 2 行，对应输入第 8 行的 ls 命令，此时 file2 文件在暂存区中，file1 文件在 cmt1 中；

输出的第 3 行，对应输入第 11 行的 ls 命令，此时刚删除了 file1 文件并进行了提交，只有 file2 是可以读取的；

输出的第 4 行，对应输入第 13 行的 read 命令，此时已经切换到了 cmt1 上，因此可以成功读取出 cmt1 中保存的 file1 的内容；

输出的第 5 行，对应输入第 19 行的 ls 命令，此时刚刚创建完 cmt3，可以读取的文件包括 file1 和 file3；

输出的第 6 行，对应输入第 21 行的 ls 命令，此时切换回了 cmt2，可以读取的文件只有 file2；

输出的第 7 行，对应输入第 23 行的 ls 命令，此时刚进行完 merge 操作，可以读取到的文件包括 file1、file2 和 file3；

输出的第 8 行，对应输入第 24 行的 read 命令，此时刚进行完 merge 操作，读取到的 file3 的内容为 cmt3 中保存的 file3；

输出的第 9 行，对应输入第 28 行的 read 命令，此时可以在暂存区中读取到 file3 的内容。此时 file3 文件的内容由 cmt3 中 file3 文件的内容，加上输入第 26 行的写入操作共同构成。

43
write file1 5 2
aa
write file2 2 2
bb
read file2 0 3
ls
commit cmt1
write file2 0 1
c
write file3 3 1
d
unlink file2
commit cmt2
read file3 0 5
commit cmt3
write file3 3 1
e
write file4 0 2
ff
commit cmt3
read file4 0 5
checkout cmt2
ls
unlink file4
unlink file2
read file1 0 5
unlink file1
ls
write file4 2 2
gg
write file1 3 2
hh
read file1 0 5
checkout cmt3
write file2 4 2
ii
unlink file1
commit cmt4
merge cmt4 cmt5
merge cmt3 cmt5
ls
read file4 0 5
unlink file4
merge cmt4 cmt6
write file1 8 1
j
commit cmt6
read file1 0 10
checkout cmt5
write file3 1 1
k
write file4 2 1
l
read file1 0 10
ls

..b
2 file1 file2
...d.
ff...
2 file1 file3
.....
1 file3 file3
...hh
3 file2 file4
..gg.
........j.
..........
3 file2 file4

样例 3 解释

在此样例中，最后得到的提交关系和每个提交中的内容与图 1 相同。

子任务

本题目当中包含 11 个子任务，每个子任务包含的命令类型、测试规模、分值如下表所示：

子任务编号	包含命令类型	规模	分值
1	read+write	小规模	10
2		大规模
3	read+write+unlink+ls	小规模
4		大规模
5	read+write+unlink+ls+commit	小规模
6		大规模
7	read+write+unlink+ls+commit+checkout	小规模	8
8		大规模
9	read+write+unlink+ls+commit+checkout+merge	小规模
10		大规模
11		超大规模

下方表格中总文件数量为 write 命令中所出现过的不同文件名的个数。表格中所有文件的总大小为整个系统中所有文件的大小之和。

如样例 2 中，总共包括 6 个文件（其中包括一个暗文件），所有文件的总大小为这 6 个文件的大小之和。

数据规模	小规模	大规模	超大规模
最大文件大小	1 KB	256 KB	2 MB
总文件数量	$10^3$	$5\times 10^3$
总命令数量		$10^4$	$2\times 10^4$
读写命令中的长度	$100$
所有文件的总大小	100 MB	1 GB	1.5 GB

提示

这里是一些非常温馨的提示：

1. 高级命令使得文件操作比较复杂。建议先实现最基本的文件读写，随后通过迭代的方法逐步增加高级功能。
2. 本题目的部分测试点规模较大，在选择编程语言和输入输出方式时请考虑程序运行和输入输出的效率。