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

aaron0919 · 2026-10-22 14:33:53 · 题解

VP 时场切了。因为做过模板。话说这题除了交互实现和多了个二分几乎和 P8126 一模一样，怎么这个就黑了呢？

首先这几乎是并行排序板板题。P8390 是打表版的板板题。P8126 是不同交互方式的板板题。搜一下应该都有我的题解……

这题提示是很明显的，考虑 n=5，发现链和菊花都是问不出任何东西的，只有一个挂了长为二的链的菊花是有用的。

我们发现可以询问一个两层的菊花，只要不选根就能知道每个点对的大小关系。

怎么保证不选菊花呢，先特判全 0，否则肯定可以只花一次询问问出一对 a_p\le a_q。

那么我们让 a_p 作为根，挂一个单点 a_q，保证不会选 a_p。

然后下面就可以挂若干点对，每次可以询问将近 n/2 对点对的大小关系，这是并行排序的模板。

对于这题下面挂的点不是偶数等照样可以直接补一些虚点变成二的幂。

然后就是只用 lg(lg+1)/2 轮就可以排序了，排序最后再讲。

对于 a_p,a_q 我们还要把这两个点插回去，如果直接二分两次那么次数是 1+55+10\times2>70，考虑用上面那个二层菊花模型换其他一对点来一次比两个，那么只用同时二分了，如果两者的 mid 靠的进就分开问，总之绰绰有余。

来介绍一下我花了 5 天的学的双调排序以及被其他题解都是一笔带过的证明。

这题利用上述二层菊花的结构我们实际上可以进行对两个数的排序，或者说任选 i,j 让 (a_i,a_j)\gets(\min(a_i,a_j),\max(a_i,a_j))。

由于我们无法得知 a 的具体信息以及题目要求并行，那么根据操作，我们希望设计一种能够分离值域的排序方式。

首先我们定义循环双调序列为若序列进行循环位移后能分割成两个（弱）单调的序列。

那么对于一个长度 2n 的循环双调序列 a，我们定义操作 split_{\max}(a)=\{\max(a_i,a_{n+i})\}_{i=1}^n，定义及以下讨论对 split_{\min} 同理。

接下来我们先证明 split_{\max} 操作就是从 2n 个数中筛选出最大的 n 个数，且很容易发现这个操作是可以并行（同一轮）处理的。

为了方便讨论，我们将 a 0-1 化，也就是选定一个 v 让 a_i\gets[a_i\ge v]，对于本题可以通过 0-1 原理推广到任意情况。

那么操作就变成 split_{\max}(a)=\{a_i\lor a_{n+i}\}_{i=1}^n，我们令 b=split_{\max}(a)。

因此当 \sum a\le n 时，a 中的 1 一定在环上连续，那么每一对 (i,n+i) 至多有一个 1，因此 b 中恰好有 \sum a 个 1；否则当 \sum a>n 时一共有 2n-\sum a<n 个 0，那么每一对 (i,n+i) 至多有一个 0，因此 b 中不能存在 0。

那么 split 操作就可以分离值域，接下来证明 b 也是循环双调序列。

一样分讨。当 \sum a\le n 时，上述的过程可以看作一个长为 2n 的环折叠成 n 的环，1 之间既不会断开也不会重叠，因此 b 上的 1 也是连续的即是循环双调序列；否则当 \sum a>n 时 b 全为 1 也是循环双调序列。

那么我们操作已经搞出来了排序算法也就很简单了。

交互部分是简单（恶心）的，建议实现玩去做我给的另外两道例题。