题解：P15587 [KTSC 2026] 排序 / Sorting

· · 题解

考虑比较 a_x 和 a_y 的大小关系。不难注意到只需要一个形如菊花的东西，即有一个中心点 u，与所有 \neq x 且 \neq y 的直接相连，然后连边 (u,x),(x,y)，大概率最大权独立集没有选 u，此时可以直接确定 a_x,a_y 大小关系，否则意味着 a_u \geq \sum \limits_{i \in [n]\setminus \{u,x,y\}} a_i，取任意一个 [n] \setminus \{u,x,y\} 内的作为中心点再询问一次即可。

进一步可以并行比较若干对 (x_1,y_1),(x_2,y_2),\cdots,(x_m,y_m)，要求每个数在所有二元组中最多出现一次。只需要 u 外面挂长度为 2 的链做类似的操作即可。

初始选定两个中心备选点 1 和 2，对 [3,n] 可以做并行比较，最多一次操作花费在中心点切换上。

现在考虑先对 [3,n] 内的所有数排序，支持并行比较。这个问题等价于得到一个深度较小的 Sorting Network。存在深度为 O(\log n) 的 Sorting Network，但常数过大且结构繁琐一般仅用于理论研究。

更简单的存在一个深度为 O(\log^2 n) 的 Sorting Network，进一步其深度为 \dfrac{\log n(\log n + 1)}{2}，其名为 Bitonic Sorting Network。

其大致过程如下：

定义：一个序列是 Bitonic 序列当且仅当其存在一个循环移位满足其先单调不降后单调不升，即其存在一个循环移位满足存在一个位置使得将这个位置劈开后前缀单调不降后缀单调不升。

Lemma：

可以 O(\log n) 次并行比较将一个 Bitonic 序列排序为单调不降序列。

Proof：

取 d = \lfloor \dfrac{n}{2} \rfloor，比较 (1,d+1),(2,d+2),\cdots,(d,2d)，每一次比较若前者大于后者则交换。不难说明此时前半部分和后半部分均为一个 Bitonic 序列，递归成两个规模为 \dfrac{n}{2} 的子问题求解即可。

操作次数满足 T(n)=1+T(\dfrac{n}{2})，故 T(n)=O(\log n)。

\square

对于长度为 n 的序列排序，先将前一半递归按照非递减排序，后一半递归按照非递增排序，将两部分拼接得到了一个 bitonic 序列，按照上述方法合并。对 n 个数排序的次数满足 T(n)=O(\log n)+T(\dfrac{n}{2})，得 T(n)=O(\log^2 n)，进一步可以确定操作次数恰为 \dfrac{\lceil \log_2 n\rceil(\lceil \log_2 n\rceil+1)}{2}，计算可得操作次数为 55。加上一次额外的切换中心点，需要 56 次操作。

剩余问题是将 1 和 2 插入序列中，由于 [3,n] 顺序已确定，切换中心点所需额外次数是不必要的。直接两次二分需要 2\log n，显然这样的二分也可以并行，故我们在 \dfrac{\lceil \log_2 n\rceil(\lceil \log_2 n\rceil+1)}{2}+\lceil \log_2 n\rceil + O(1) 次询问内解决了原问题。