题解：Luogu P9961 [THUPC 2024 初赛] 排序大师

题意

给定长度为 \(n\) 的排列 \(p\)，每次操作可以选择 \(i,j,k,l\) 满足 \(1\leq i\leq j<k\leq l\leq n\)，交换 \(a_{i\sim j}\) 和 \(a_{k\sim l}\)。。求最小操作次数使得 \(p\) 单调递增。\(1\leq n\leq 2\times 10^3\)。

题解

大神题。

排列中的交换问题，自然地想到从图论的角度刻画。套路地考虑从 \(i\) 向 \(p_i\) 连边，但是这样每次操作变化的边很多，难以刻画性质。这启发我们的建模要去适应本题的操作，使得每次操作的变化的边数是常数级别的。可以想到从 \(p_{i-1}\) 向 \(p_i\) 连边，这样每次操作至多会改变 \(4\) 条边，但是我们希望从环的角度分析问题，而终态是一条 \(1\sim n\) 的链，不利于分析。我们可以令 \(p_0=0,p_{n+1}=n+1\)，从 \(p_{i-1}+1\) 向 \(p_i\) 连边，这样终态是 \(n+1\) 个自环，性质就很好了。

接下来考虑刻画本题的操作。不妨先假设 \(j+1\leq k-1\)。

\[p_{0\sim i-1}\qquad p_{i\sim j}\qquad p_{j+1\sim k-1}\qquad p_{k\sim l} \qquad p_{l+1\sim n+1}\\ \downarrow\\ p_{0\sim i-1}\qquad p_{k\sim l}\qquad p_{j+1\sim k-1}\qquad p_{i\sim j} \qquad p_{l+1\sim n+1} \]

如上图所示，此时 \((p_{i-1}+1,p_i),(p_{j}+1,p_{j+1}),(p_{k-1}+1,p_{k}),(p_{l}+1,p_{l+1})\) 四条边在操作后会变成 \((p_{i-1}+1,p_k),(p_l+1,p_{j+1}),(p_{k-1}+1,p_i),(p_j+1,p_{j+1})\)。我们可以将操作视作先交换 \((p_{i-1}+1,p_i),(p_{k-1}+1,p_{k})\) 这两条边的出点，再交换 \((p_{j}+1,p_{j+1}),(p_{l}+1,p_{l+1})\) 这两条边的出点。考虑交换两条边的出点带来的影响，手玩可以得出，若这两条边处于同一个环中，则该环会分裂为两个环，否则两条边所处的两个环会合并成一个环。因此交换出点只会令环数 \(+1\) 或 \(-1\)，于是一步操作只会令环数 \(+2\) 或 \(-2\) 或保持不变。

再来考虑操作为 \((i,j,j+1,k)\) 的情况。

\[p_{0\sim i-1}\qquad p_{i\sim j}\qquad p_{j+1\sim k}\qquad p_{k+1\sim n + 1}\\ \downarrow\\ p_{0\sim i-1}\qquad p_{j+1\sim k}\qquad p_{i\sim j}\qquad p_{k+1\sim n + 1} \]

如上图所示，此时 \((p_{i-1}+1,p_i),(p_j+1,p_{j+1}),(p_k+1,p_{k+1})\) 三条边在操作后会变成 \((p_{i-1}+1,p_{j+1}),(p_k+1,p_i),(p_j+1,p_{k+1})\)。此时操作可以视作先交换 \((p_{i-1}+1,p_i),(p_j+1,p_{j+1})\) 的出点，再交换 \((p_j+1,p_i),(p_k+1,p_{k+1})\) 的出点，因此一步操作同样只会令环数 \(+2\) 或 \(-2\) 或保持不变。

设初始状态下有 \(c\) 个环，则操作次数的下界显然为 \(\left\lceil\dfrac{n+1-c}{2}\right\rceil\)。考虑能否构造特定操作，使得每次操作环数都会 \(+2\)，这样就能取到下界。

考虑一个挺牛的构造：取最小的 \(x\) 使得 \(x\) 前面存在 \(>x\) 的数，再取 \(y\) 为 \(x\) 前面最大的数。此时 \(x-1\) 必然在 \(y\) 之前，\(y+1\) 必然在 \(x\) 之后，也就是整个排列形如

\[\cdots\quad x-1\quad\cdots\quad y\quad\cdots\quad x\quad\cdots\quad y+1\quad\cdots \]

我们执行操作 \((pos_{x-1}+1,pos_y,pos_x,pos_{y+1}-1)\)，那么整个排列就变成了

\[\cdots\quad x-1 \quad x\quad \cdots\quad y\quad y+1\quad\cdots \]

注意到我们操作的是 \(x\) 的入边和出边与 \(y+1\) 的入边和出边，而操作后新产生了 \(x\rightarrow x\) 和 \(y\rightarrow y\) 两个自环，因此环数一定 \(+2\)。

这样我们就完成了构造。每次操作前，用单调栈维护每个数前面比它大的数的个数，找出最小的 \(x\) 后直接做就行了。时间复杂度是 \(\mathcal{O}(n^2)\)。

代码很好写，就不放了。