P8859 冒泡排序 Sol

· · 题解

按之前说的来写一篇详细一点的题解。

对于 type=1，如果一个数前面有比它更大的数，那这个数必须要进行操作。定义 f_{i,j} 表示从大到小插入第 i 个数，需要操作 j 次使得其升序排序的排列数。第 i 个数如果放在开头则不需要操作，否则必须多操作一次。转移式即 f_{i+1,j} \overset{+}{\gets} f_{i,j},f_{i+1,j+1} \overset{+}{\gets} i\times f_{i,j}（事实上，这就是第一类斯特林数）。

对于 type=2，我们先固定掉最大值的位置，比如将其放在最后一个位置。将这个圆排列强制变成排列，依用上面的方法，所有满足在这个位置上的数比前面的数都大的位置个数就是不需要操作的位置的个数。这样的数显然是更新了前缀的最大值，这引导我们想到笛卡尔树，不需要操作的位置的个数就相当于笛卡尔树上左链上点的个数。下面给出一个实例，例如 p=(3,1,2,5,4,7,6,8)：

容易发现，3,5,7,8 不需要操作。

接下来要处理位移的问题。一次位移相当于把最左边的数挪到最右边去。最左边的数在笛卡尔树上表现为左链上最下面的点，挪到右边相当于放到根的右子树。先不考虑放到右边的表现，注意到 3 挪走之后，其右子树成为 3 父亲新的左子树。从此可以看出，位移操作相当于将左链底的点挪到最右，并用其右子树替代这个点。最大可以节省的操作次数就是在所有通过位移能达到的状态中，左链上点的个数的最大值。

同时启发我们不用考虑被挪到右边去了会发生什么，因为其必然会操作，不管就行了。

分析这个最大值是什么，可以发现就是从根到某个点向左子树走的最多的次数加一。例如上面的例子中，8 \to 1 总共向左子树走了四次，也即不需要操作的点最多有五个，可得最少操作次数为 3。

那么现在被转成了一个数树的问题。先把 n 固定在最后面，需要统计有多少棵 n-1 个点的二叉树满足从根到某个点向左子树走的最多的次数为 n-k-1。定义 g_{i,j} 表示 i 个点的二叉树可以节省的最多操作次数为 j。每次枚举左子树和右子树能节省的操作次数，记为 p,q，那么新的树能节省的操作次数即为 \max(p+1,q)。这样枚举 i 并枚举左子树的大小 j，以及左右子树对应的 p,q 可以得到一个 O(n^4) 的做法（同时要带一个 \dbinom{i-1}{j} 的系数，表示 i 个数中，除去最值选 j 个数来构成左子树，右子树就用剩下的）。

这个东西暴力写出转移之后，发现这个东西可以采取前缀和优化的方法去掉一个 p,q 的枚举。具体方法是直接枚举 \max(p+1,q)，从前缀和转移到前缀和，差分求出原始的 g。

完整代码。