【MX‑S15‑T2】「DLESS‑5」宇宙射线

P16996 【MX‑S15‑T2】「DLESS‑5」宇宙射线 - 洛谷

给出一个 $n$，并给出 $1 \sim n$ 的排列 $a$，问在冒泡排序的某一次的执行是相反的，问最终能产生的本质不同的 $a$ 的数量。

$1 \le n \le 2 \times 10 ^ 6, 1 \le a_i \le n$。

学校模拟赛 T2，全世界都把这个题切了，除了我。我的这篇题解的思路来自学弟 @Zjh6666，膜拜。

在阅读本篇题解之前，最好先独立思考关于这个题目的做法。

本文所讨论的序列默认为排列。

冒泡排序的本质

冒泡排序的本质是在每一轮的操作中，从一个未排序的前缀中找出最大的值，将其推到当前这段前缀的末尾。

形式化的讲，对于第 $r$ 轮，后面的 $i \in [n - r + 2, n]$ 时，$a_i = i$。而对于前面的 $[1, n - r + 1]$ 是未正确排序的。而我们本轮的操作就是找到 $\max_{i \in [1, n - r + 1]} a_i$，并将其推到 $n - r + 1$ 的位置。

考虑最终态

知道了冒泡排序的本质之后，我们实际上就可以分析出来这个题的最终态。

对于 $1 \sim r - 1$ 轮，排序是无错的，但考虑到如果在第 $r$ 轮时，操作被宇宙射线照射，那么就存在一个 $x$，被推到 $n - r + 1$，并永久固定。对于 $r + 1 \sim n - 1$ 轮继续执行无错的冒泡排序。

结论

由最终态我们可以得到，最终的排列 $a$ 完全由二元组 $(k, x)$，即 $x$ 在第 $k$ 轮被固定在了位置 $n - k + 1$，最终得到的序列的形式如下：

$$a_{(k, x)} = \{ 1, 2, \dots, x - 1, x + 1, \dots, n - k + 1, x, n - k + 2, \dots , n \}$$

这个序列被清晰的分为三段：

• $[1, n - k]$ 位：最后 $n - k + 1$ 轮，由刨除 $x$ 之外的剩下的 $n - k$ 个数形成的完全升序的序列。
• $n - k + 1$ 位：第 $k$ 轮的宇宙射线使得 $x$ 被推到 $n - k + 1$ 的位置。
• $[n - k + 2, n]$ 位：前 $k$ 轮的排序，使得这段完全升序。

如何统计二元组？

考虑分类讨论关于二元组 $(k, x)$ 的贡献。

升序态

考虑唯一一次的宇宙射线没有对序列的冒泡排序产生影响。这样我们的序列最终就能达到完全升序的情况。这里我们只需要构造出任意一种合法的方案即可以升序。

考虑自愈的情况，即就算射线造成影响，也依然能做到在后面的冒泡中自愈。这种情况，当且仅当第 $n - x + 1$ 轮的最大的数 $x$ 没有被射线影响，依然正常归位。

而归位的条件就是当前需要归位的 $x$ 在序列中的位置 $\ge 3$，定义 $x$ 初始的位置在 $pos_x$，则可以表述为 $pos_x \ge n - x + 3$。

因此如果对于任意一个 $x$ 满足上述的等式，则完全升序成立。记 $1$ 的贡献。

相邻态

即最终的形态只是相邻的两个位置发生了错误的互换，这种情况当且仅当在某一轮的最后一次互换时发生宇宙射线。

具体来说，对于第 $k$ 轮，最大值应为 $n - k + 1$，但是此时变成了 $n - k$，则最终的序列为：

$$a_{(k, n - k)} = \{ 1, 2, \dots, n - k - 1, n - k + 1, n - k, n - k + 2, \dots \}$$

即 $n - k + 1$ 和 $n - k$ 受宇宙射线影响交换。这种操作可以在每一轮进行，则固定有 $n - 1$ 次贡献。

跨越态

对于当前的第 $k$ 轮，既不是 $n - k + 1$，也不是 $n - k$ 被移动到最右端，而是 $x < n - k$ 的数被移动到了本轮的最右端。

此时的序列形态和我们所说的传统态是一样的：

$$a_{(k, x)} = \{ 1, 2, \dots, x - 1, x + 1, \dots, n - k + 1, x, n - k + 2, \dots , n \}$$

$x$ 数跨越了 $[x + 1, n - k + 1]$ 位置的所有值，一路向右被固定在 $n - k + 1$ 的位置。

我们换视角，考虑对于一个元素 $x$ 做贡献的情况，若 $x$ 能产生跨越的贡献，则一定是后缀最大值，则能在 $[x + 2, n]$ 的位置产生贡献，此时记 $n - (x + 2) + 1 = n - x - 1$。

为什么一定是后缀最大值？
如果 $x$ 右边存在一个 $y > x$，那么在错误发生之前的正常冒泡过程中，$y$ 会被推到 $x$ 的右边并优先参与后续归位，因此 $x$ 不可能在错误发生的那一轮成为被错误推到末端的元素。

因此对于答案的统计，我们维护后缀最大值，每次如果有当前值大于后缀最大值，说明后面的位置都可以用，贡献即 $\sum_{a_i \text{是严格后缀最大值}} \max(0, n - a_i - 1)$。