CLICK HERE(LINK)

$\large\text{Outline}$

• 基于排序算法的构造。

$\large\text{Algorithm}$

• 洗牌这个操作对整体序列的影响比较大，不方便直接操作，解决这道题的第一步还是需要转换操作。

• 容易得到如下转换：将原排列分成 $k$ 段并对这 $k$ 段区间进行 reverse 等价于将 $k$ 段区间分别 reverse 后整体 reverse。

• 例如序列 $\texttt{[1,3,5,2,4,6]}$，假设分段为 $\texttt{[1],[3,5,2],[4,6]}$，原本操作的预期结果为 $\texttt{[4,6],[3,5,2],[1]}$，现在我们现将这几段区间分别 reverse，得到 $\texttt{[1],[2,5,3],[6,4]}$，再将排列整体 reverse，也可得到 $\texttt{[4,6,3,5,2,1]}$。

• 这一步操作的好处在于能使排列的整体操作变得不关键，显然我们只需关注当前翻转的区间，这为分治提供了基础。

• 接下来套路化地，我们应该考虑某种 $\Theta(n\log n)$ 复杂度的排序算法。

• 除去基数排序、堆排序、锦标赛排序等等需要借助数据结构辅助的算法。可选择的无非归并排序和快速排序。

• reverse 的性质貌似不能支持归并操作。考虑快排。

• 对于一般序列的快速排序，我们一般根据随机数据的性质随机一个点 $x$ 作为分界线，将 $\leq x$ 的点放到 $x$ 左侧，反之放到右侧，此时的时间复杂度期望是 $\Theta(n\log n)$ 的。

• 对于排列或排列中 $[l,r]$ 区间内的全部元素构成的序列，我们只需要钦定 $x$ 为 $mid$ 即可。

• 每次钦定处理当前层，将 $\leq mid$ 放到左侧，反之放到右侧，然后递归处理 $[l,mid]$ 和 $[mid+1, r]$ 即可（注意它们的操作应当是同时进行的）。

• 因此我们只需要考虑每一层“将 $\leq mid$ 放到左侧，反之放到右侧”这一操作如何进行。

• 我们把序列中小于 $mid$ 的元素标记为 $0$，大于 $mid$ 的标记为 $1$ 可以得到一个 $01$ 序列，例如：

\[1011100110101\]

• 显然连续的一段 $0,1$ 在 reverse 操作中被整体地选取是更优的，基于此，我们可以将连续的 $0,1$ 合并，转换得：

\[101010101\]

• 由于 $01$ 交错出现，我们容易通过 reverse 操作合并更多的 $01$。一种显然的构造策略为把整个序列分成若干长度为 $3$ 的区间，交换其中第二个元素和第三个元素，上文中的序列可以交换得到：

\[1\color{blue}10\color{black}0\color{blue}01\color{black}1\color{blue}10 \\ \rightarrow \color{orange}1\color{black}0\color{orange}1\color{black}0\]

• 标记为蓝色的点为被交换的点，黄色标记了为 $1$ 点交换后的合并。

• 我们可以发现每次进行这样的操作后序列中元素个数会变成原来的 $\lceil\frac{1}{3} \rceil$。因此处理一个分治区间的操作数量是 $O(\log_3 (r-l+1))$ 的。

• 需要特别注意的是，当序列中只剩两个元素时，要特判一下，若序列中 $0$ 在 $1$ 前，进行一次整体 reverse。

• 总共分治 $O(\log_2 n)$ 层，注意到分治的左右两边的操作需要同步进行，因此操作次数为 $T(n)=T(\frac{n}{2})+(\log_3n+a)$（$a$ 为余数区间和序列元素剩余两个的情况造成的常数），可得操作次数数量级为 $\Theta(\log^2n)$。

$\large\text{Notes}$

• 以排序为目的的构造的题目的思路一定是魔改已有排序算法。
• 就个人而言，方便处理同一层的多个区间，实现推荐使用 $\text{BFS}$。而且常数小。