题解

问题分析

本题要求通过交互操作（移动左右手位置并比较牌的大小）确定一副打乱的牌的具体排列（每张牌的大小为0到n-1的唯一值）。初始时左右手均在位置0，每次可移动左右手（上下各一张）或比较当前位置的牌，需在7.0×10⁸次移动内完成。

核心思路

算法的核心是分治+归并排序：通过递归将牌的位置区间划分为子区间，分别求解子区间的有序排列（即按牌大小从小到大的位置顺序），再将有序子区间合并为更大的有序区间，最终得到整个区间的有序排列，进而反推出每张牌的大小。

关键挑战是减少移动次数：合并子区间时需频繁比较不同位置的牌，直接移动指针会导致大量无效移动。因此引入类似莫队算法的优化——通过合理排序比较查询的顺序，最小化左右手的移动距离。

算法步骤

1. 分治划分区间：
   定义solve(l, r)返回区间[l, r]内按牌大小从小到大排序的位置列表。递归地将[l, r]分为[l, mid]和[mid+1, r]，分别调用solve得到两个有序子列表a和b。

2. 归并有序子列表：
   merge(a, b, len)函数将两个有序子列表a和b合并为一个有序列表。为减少比较次数，采用以下优化：

   • 若a的长度大于b，交换两者（小列表合并更高效）。
   • 提取b的奇数索引元素组成bi，先合并a和bi得到ab（减少后续比较量）。
   • 收集需要比较的(x, b[r])对（x来自ab，b[r]为b的偶数索引元素），按莫队算法思想排序（分块+奇偶排序），减少左右手移动次数。
   • 根据排序后的比较结果，合并ab和b的剩余元素，得到最终有序列表。

3. 比较操作的实现：
   comp(x, y)函数通过移动左右手到位置x和y，调用cmp()获取比较结果。通过莫队排序优化比较顺序，使左右手移动总距离最小化。

4. 生成结果：
   最终得到的有序位置列表pos中，pos[i]表示大小为i的牌所在的位置。因此结果数组res满足res[pos[i]] = i，即res[j]为位置j的牌的大小。

代码解析

• 分治递归（solve函数）：将区间二分，递归求解子区间的有序位置列表，基础 case 为单元素区间（直接返回该位置）。
• 归并优化（merge函数）：通过拆分b为奇数索引子数组bi，先合并a与bi，再处理剩余元素，减少比较次数；收集比较查询并按莫队规则排序（块大小B动态计算），降低移动成本。
• 比较与移动（comp函数）：调整左右手位置到目标x和y，调用cmp()返回比较结果，确保移动操作的必要性（仅当当前位置不符时移动）。
• 结果生成：利用有序位置列表pos反推每个位置的牌大小，得到最终答案。

复杂度分析

• 比较次数：归并排序的比较次数为O(n log n)，符合题目中cmp()调用不超过10⁷次的限制（n≤1.5×10⁵时，n log n≈1.5×10⁵×18≈2.7×10⁶）。
• 移动次数：通过莫队算法优化比较顺序，移动次数为O(n√n)（块大小为√n时），对于n=1.5×10⁵，√n≈387，总移动次数约1.5×10⁵×387≈5.8×10⁷，远低于7.0×10⁸的限制。

综上，算法通过分治归并与莫队优化，高效完成了交互查询与排序，满足移动次数约束，适用于大规模输入。