1.题目大意

给定一个长度为 $n$ 的排列 $x_1, x_2, \dots, x_n$，其中包含 $1$ 到 $n$ 的每个数字恰好一次。我们需要通过 $n-1$ 轮操作来修改这个序列，第 $k$ 轮（$k = 2, 3, \dots, n$）可以选择交换 $x_k$ 和 $x_{\lfloor k/2 \rfloor}$，或者什么都不做。

目标是找到通过这种操作方式能够得到的字典序最小的序列。

2.算法思路

关键观察

完全二叉树结构：

操作规则对应一棵完全二叉树，节点编号从 $1$ 到 $n$

节点 $i$ 的父节点是 $\lfloor i/2 \rfloor$

第 $k$ 轮操作只能交换节点 $k$ 与其父节点

字典序最小原则：

要使得整个序列字典序最小，需要从左到右依次确定每个位置能放的最小可能值

前面的位置确定后，后续位置的调整受到限制

操作特性：

操作只能从子节点向上交换，不能从父节点向下交换

这限制了值的移动方向，只能从深层节点向浅层节点移动

贪心策略

从根节点（下标 1）开始，逐层向下处理每个节点：

对于每个节点 $i$，考虑三个值：

当前节点的值 $x[i]$

左子节点的值 $x[2i]$（如果 $2i \leq n$）

右子节点的值 $x[2i+1]$（如果 $2i+1 \leq n$）

决策过程：

如果当前节点值已经是最小值：

不进行任何交换

继续处理子节点

如果左子节点值是最小值：

交换当前节点与左子节点的值

这个交换会在后续的第 $2i$ 轮操作中执行

如果右子节点值是最小值：

交换当前节点与右子节点的值

这个交换会在后续的第 $2i+1$ 轮操作中执行

关键：交换后可能需要调整左右子树顺序以保证整体字典序最优

代价计算与子树调整 为了做出最优决策，我们需要计算将某个特定值换到某个子树根节点所需的最小交换次数。

记忆化搜索函数 get(i, val)：

功能：计算在子树 $i$ 中，把值 val 换到根节点 $i$ 所需的最小交换次数

基础情况：如果 $i$ 是叶子节点，返回 0（无法交换）

递归过程：

比较 val、左孩子值、右孩子值的最小值

根据最小值所在位置决定递归方向

比较左右子树的交换代价，选择代价较小的路径

子树顺序调整：

当右子节点的值最小时，交换后需要决定左右子树的相对顺序

通过比较 get(left, min(val, x[left])) 和 get(right, min(val, x[right])) 来决定

选择交换代价较小的子树放在左边，以获得更好的字典序

复杂度分析

记忆化搜索状态数：$O(n \log n)$

每个节点 $i$ 最多与 $\log n$ 个不同的 val 值相关

总状态数在 $n \log n$ 级别

时间复杂度：$O(n \log n)$

每个状态的计算是常数时间（借助哈希表）

可以处理 $n \leq 2 \times 10^5$ 的数据规模

空间复杂度：$O(n \log n)$

用于存储记忆化搜索的结果

算法正确性

贪心选择的正确性：

字典序要求使得我们必须优先保证前面位置的值尽可能小

通过逐层处理，确保每个位置都放置了在当前约束下可能的最小值

交换代价计算的必要性：

单纯选择当前最小值可能影响后续位置的优化空间

通过计算交换代价，在多个可选方案中选择对后续影响最小的

记忆化搜索的优化：

避免重复计算相同子问题的交换代价

保证算法在合理时间内完成

3.总结

本题是一道结合了完全二叉树结构、字典序贪心和记忆化搜索的综合性题目，其主要特点：

问题转化：将序列操作问题转化为树形结构上的值交换问题

贪心思想：基于字典序要求，采用从左到右的贪心策略

动态规划：使用记忆化搜索计算子树调整的代价

优化决策：通过代价比较在多个可行方案中选择最优解

这种"树形结构 + 贪心 + 记忆化"的解题模式在算法竞赛中很常见，需要选手对问题结构有深刻理解，并能够设计合适的数据结构和算法来高效解决问题。