洛谷的测试数据仅供民间交流使用，非官方测试数据。官方评测链接：https://www.cspro.org/。
西西艾弗岛运营公司是一家负责维护和运营岛上基础设施的大型企业。在公司内，有许多分管不同业务的部门都需要使用到服务器设施。为了便于管理，同时降低公司运行成本，西西艾弗岛运营公司建设了一套私有云系统。这套私有云系统除了能提供托管的虚拟机服务外，还能提供一些其他的服务。其中，最受好评的当属日志服务。此前，各个业务系统的日志都是分散存放在各自的服务器上的， 这样不仅不方便查看和分析而且也有丢失的风险。而日志服务则能够将各个业务系统的日志统一收集起来，方便查看和管理。
日志服务器收集到的日志都是纯文本，且高度格式化。这意味着日志数据可以被压缩得非常小。但是日志数据量非常大，且对处理效率的要求较高，因此可以牺牲一定的压缩率，使用高效的压缩算法来压缩日志数据。小 C 被安排来实现解压缩日志的程序，给定一段被压缩的日志数据，他需要将其解压缩。
这种压缩算法产生的数据流，可以被视为是一系列的元素。元素分为两种：字面量和回溯引用。字面量包含一系列的字节，对其进行解压缩时，直接将这些字节输出即可。回溯引用则是将此前已经解压缩得到的数据流的一部分重复输出。回溯引用可以表示为 ，包含两个数字，分别为偏移量 和长度 。偏移量表示从当前位置向前回溯的距离，长度表示需要重复输出的字节数。其中要求 。若已经解压缩了 字节，当 时，表示重复输出自偏移量 （首个字节偏移量为 ）开始的 个字节。例如，已经解压缩的数据流是 abcde，则回溯引用 表示输出 cd。当 时，表示重复输出自偏移量 开始的的 个字节，然后继续反复输出这 个字节，直到共输出 个字节。例如，已经解压缩的数据流是 abcde，则回溯引用 表示输出 deded。
被压缩的数据格式分为两部分：导引域和数据域。其中导引域保存了原始数据的长度。设原始数据长度为 。则 可以表示为 ，其中 ，且 。导引域的长度为 字节，依次保存 。即每个字节用低 位保存 ，除了最后一个字节的最高位为 ，其余字节的最高位为 。例如，原始数据的长度为 ，那么 依次为：，即 进制的 0x2C、0x0A。因此引导区的长度为 ，字节序列为 0xAC 0x0A。
:::align{center}
:::
数据域保存了被压缩后的数据，是连续存储的元素的序列。每个元素的第一个字节的最低两位表示了元素的类型。当最低两位为 时，表示这是一个字面量。如果字面量包含的字节个数为 ，且 ，那么第一个字节的高 位表示 。随后的 字节即为字面量所包含的原始字节。例如字节 0xE8，其二进制为 1110 1000，低二位是 ，表示这是一个字面量。高六位是 111010，表示数字 ，即表示该字面量包含 个字节。因此，该字节后面的 个字节即为字面量所包含的原始字节。如果 ，那么则将 用小端序的 至 个字节表示，存储于第一个字节的后面。第一个字节的高六位存储的值为 或 时，分别代表 用 或 个字节表示。例如，字节序列 0xF4 0x01 0x0A 中，首字节的二进制为 1111 0100，低二位是 ，表示这是一个字面量。高 位是 111101，表示数字 ，即表示随后有两个字节存储了字面量的长度。随后的两个字节 0x01 0x0A，按小端序组成了十六进制数 0x0A01，即十进制 ，表示该字面量包含 个字节。随后的 个字节即为字面量所包含的原始字节。
:::align{center}
:::
当元素首字节的最低两位是 01 时，表示这是一个回溯引用 ，且 。此时， 占 位，其低 位存储于随后的字节中，高 位存储于首字节的高 位中。 占 位，存储于首字节的 至 位中。如下图所示：
7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0
+-----+-----+-+-+ +----------------+
|o(h3)| l-4 |0|1| |o (lower 8 bits)|
+-----+-----+-+-+ +----------------+
例如，字节 0x2D 0x1A，其首字节的二进制为 001 011 01，其最低两位为 01，表示这是一个回溯引用，其中 至 位是 011，表示数字 ，意味着 ，即 。其高 位是 001，与随后的字节 0x1A 组成了十六进制数 0x11A，即十进制 ，表示 。因此，该回溯引用是 。
:::align{center}
:::
当元素首字节的最低两位是 10 时，表示这是一个回溯引用 ，且 。此时， 占 位，以小端序存储于随后的两个字节中。 占 位，存储于首字节的高 位中。例如，字节 0x3E 0x1A 0x01，其首字节的二进制为 0011 1110，其最低两位为 10，表示这是一个回溯引用，其中高 位是 001111，表示数字 ，即 ，即 。随后的两个字节 0x1A 0x01，按小端序组成了十六进制数 0x011A，即十进制 ，表示 。因此，该回溯引用是 。
:::align{center}
:::
我们规定，元素的首字节的最低两位不允许是 11。如果出现了这种情况，那么这个数据域就是非法的。
压缩后的数据为合法的，当且仅当以下条件都满足：
- 引导区的长度不超过 字节；
- 引导区能被正确恢复为原始数据的长度；
- 每个元素的首字节的最低两位不是
11；
- 每个元素都能按照规则被恢复为原始数据；
- 得到的原始数据长度恰好等于引导区中编码的原始数据长度。
