透明少女

冷却心 · 2026-08-15 15:02:51 · 题解

注意到一次操作会使得序列长度翻倍，所以至多 O(\log m) 次操作后序列长度会大于等于 m。前面这部分可以直接模拟，复杂度 O(m\log m)。

当序列长度不少于 m 时，我们只关心其长度为 m 的前缀，那么在序列末尾接上的后缀可直接不管。现在问题变成，每次在序列的前面拼接上自己长度为 a_i 的前缀，问最后得到的序列的前 m 个数。

考察最终第 x 个数在原序列内的下标。从后往前考虑，若最后一次操作接上的前缀是 a_i，若 x>a_i，则他在这次操作之前位于 x-a_i，否则不变。后面以此类推。进一步地，我们直接考察整段数，答案序列中一段前缀 [1,x]，若 x>a_i，在操作 a_i 之前，分别由前缀 [1,a_i] 与 [1,x-a_i] 组成，否则不变。于是我们用一个 set 维护答案的每段，每次倒着做遇到一个 a_i 把长度大于 a_i 的段分裂，同时维护一下每段属于答案序列中的下标，最后直接输出即可。复杂度 O(m\log m)。实现很简单。