再来一小段题解¶
解法比较¶
完整构造与按需输出是并列方案：完整构造减少递归与查找开销，按需输出避免保存最大字符串。标程采用按需输出。
出题人解法先读入所有询问，求出最大版本，逐次把当前串的指定前缀复制到尾部，实际构造最大版本。各版本互为前缀，所以每次询问只需输出这个大串相应长度的前缀。设最大版本号为 \(V\) 、最大串长为 \(L_{max}\) 、询问数为 \(Q\) 、输出总字符数为 \(C\) ，时间为 \(O(V+Q+L_{max}+C)\) ，空间为 \(O(L_{max}+V+Q)\) .
Codex（GPT-6）采用的实现只保存初串和各版本长度，按拼接关系递归输出所需前缀；这种分解与完整构造中的实际复制完全等价。额外空间降为 \(O(V+|s_1|)\) ，适合本题内存限制；时间上界为 \(O(V+(C+Q)\log(V+1))\) .代价是递归和查找版本的开销，输出的 \(C\) 个字符仍然必须逐个写出，按需输出的优势在于空间。
先算长度¶
记 \(L_k=|s_k|\) ，则
用整数运算 (L + 4) / 5 实现向上取整。长度严格递增，而且每个版本都是后续版本的前缀。只需保存 70 个长度和最初的字符串。
按前缀递归输出¶
定义 PrintPrefix(t) ：输出任意一个长度至少为 \(t\) 的版本的前 \(t\) 个字符。由于较短的版本总是较长版本的前缀，选择哪个足够长的版本都不会影响结果。
- 若 \(t\le L_1\) ，直接输出 \(s_1\) 的前 \(t\) 个字符。
- 否则二分找到最小的 \(k\) ，使 \(L_k\ge t\) ，此时有 \(L_{k-1}<t\) . 所求前缀由完整的 \(s_{k-1}\) 和其前 \(t-L_{k-1}\) 个字符组成。先递归输出长度为 \(L_{k-1}\) 的前缀，再递归输出长度为 \(t-L_{k-1}\) 的前缀。
回答询问 \(x\) 时，递归输出长度为 \(L_x\) 的前缀，随后输出换行。写出的字符直接进入输出流，不在内存中保存完整的大字符串。标程的 Lengths 数组从下标 \(0\) 开始，因此版本 \(x\) 的长度存储在 Lengths[x - 1] 中。
正确性¶
初始字符串的前缀显然正确。对 \(t>L_1\) ，选出的最小版本 \(k\) 满足 \(L_{k-1}<t\le L_k\) . 根据定义，\(s_k\) 的前 \(L_{k-1}\) 个字符恰好是 \(s_{k-1}\) ，余下部分是 \(s_{k-1}\) 的前缀。两次递归的长度均小于 \(t\) ，由归纳假设输出正确，拼接后就是要求的前缀。因此每次询问都输出正确的版本。
复杂度与内存¶
设最大版本编号为 \(V=70\) ，所有询问的输出字符总数为 \(C\)（Characters，不含换行）。每次非叶递归都拆成两个非空部分，因此递归调用总数为 \(O(C+Q)\) ；每次二分花费 \(O(\log V)\) . 总时间为 \(O(V+(C+Q)\log V)\) ，额外空间为 \(O(V+|s_1|)\) ，另有标准输出流的缓冲区。
递归中的版本编号严格下降，深度至多 \(V\) . 这种输出方式无需存储数百万字符，适合本题的 8 MB 内存限制。