String and Operations 题解

思路

把字符连同它最初的位置编号一起看待，操作顺序就固定为编号 $1,2,\ldots,n$。

小规模可以保存“当前排列中的每个原编号及其字符”，依次枚举 0、U、D、L、R 五种操作并对相同状态去重，最后在所有字符序列中取字典序最小者。

为了处理更大规模，需要观察已经处理的前缀与尚未处理部分的边界。令 $F_i$ 是处理完最初的前 $i$ 个字符后，所有与后续操作有关的边界形态中字典序最小的长度 $i$ 字符串。字符 $c$ 单独进行 0、U、D 中的一种时能够达到的最小字符记为

交换只能越过当前边界附近的一个字符。分类讨论最后一次涉及边界的交换，可以证明 $F_{i+1}$ 只可能由以下四个候选取最小值得到。以下下标从 $0$ 开始，$\operatorname{pre}(x,m)$ 表示 $x$ 的前 $m$ 个字符。

1. 不跨边界交换：$F_i+g(s_i)$。
2. 当前字符向左交换：$F_{i-1}+g(s_i)+s_{i-1}$。
3. 前一个边界字符向右交换：$\operatorname{pre}(F_i,i-1)+s_i+\operatorname{last}(F_i)$。
4. 连续涉及前两个边界字符：$\operatorname{pre}(F_{i-1},i-2)+s_i+\operatorname{last}(F_{i-1})+s_{i-1}$。

不存在第五种边界次序：一个原编号在自己的操作结束后不会再次主动交换，而尚未操作的编号又只能由紧邻边界的已处理字符带动。因此更远位置的影响已经包含在 $F_i$ 或 $F_{i-1}$ 中。对同一边界形态保留字典序最小的前缀不会损失最优解，因为后续拼接和局部交换只会读取其末尾并保留更早的公共前缀。

直接存储字符串并构造、比较这四个候选需要 $O(n^2)$ 时间，足以通过第二子任务。

满分算法把字符串表示为规范化持久化线段树。每个叶子是一个字符；内部结点由左右儿子的编号唯一决定，并通过二元组查表合并。于是两个相同子串必然具有同一结点编号，不依赖随机哈希，也不存在碰撞。

上述每个候选相对某个旧版本只修改至多三个位置，所以用持久化点修改即可构造。比较两个候选时，若左儿子编号不同就递归左侧，否则递归右侧，能在 $O(\log n)$ 时间内定位第一个不同字符。每一步只有常数个候选。

做法

对每个测试用例建立覆盖 $n$ 个位置的二叉树，未使用位置填入统一哨兵字符。叶子字符和内部左右儿子对都做规范化编号。

从空版本 $F_0$ 开始，按顺序枚举 $i$。根据上面的四类边界形态，从 $F_i$ 或 $F_{i-1}$ 出发做一至三次持久化点修改；用规范树的首次不同位置比较选出最小根，保存为 $F_{i+1}$。最后逐点读取 $F_n$ 的前 $n$ 个字符。

独立复核程序直接保存普通字符串并使用同一完整分类；小规模复核程序则按原操作定义枚举带编号的排列状态。

复杂度

状态枚举算法的时间复杂度上界为 $O(5^n n)$，空间复杂度为 $O(5^n n)$。

普通字符串动态规划对每个测试用例的时间复杂度为 $O(n^2)$，空间复杂度为 $O(n^2)$。

规范化持久化线段树算法对每个测试用例的期望时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n\log n)$；期望仅来自内部结点二元组字典的常数时间查找，字符串相等与字典序比较本身是精确的。