题解：UVA11525 Permutation

naroto2022 · 2024-12-16 11:49:22 · 题解

UVA11525 题解

题面

原题传送门

前置知识

正向康托展开

题意很简单，就是求长度为 n 的数组 a 在全部 n 的排列中按字典序排序的排名。

先那一组数据来手玩：

求 4 2 3 5 1 的排名。

• 第一位是 4，在这这个排列中，还会有以 1,2,3 作为第一位，所以它会增加 3\times(5-1)!=72 的排名。
• 第二位是 2，在以 4 为第一位的排列中，还会有 1 作为第二位，所以它会增加 1\times(5-2)!=6 的排名。
• 第三位是 3，在以 4 2 为前两位的排列中，还会有 1 作为第三位，所以他会增加 1\times(5-3)!=2 的排名。
• 第四位是 5，在以 4 2 3 为前三位的排列中，还会有 1 作为第四位，所以它会增加 1\times(5-4)!=1 的排名。
• 第五位无需考虑

所以，该排列的排名为 72+6+2+1+1=82 名，记得最后要加 1，因为我们算的是该排列前面有多少个排列。

形式化的，记 s_i\gets\begin{aligned}\sum_{j=i+1}^n [a_j<a_i]\end{aligned}，则 a 的排名就为 \begin{aligned}\sum_{i=1}^n s_i\times(n-i)!\end{aligned}。

如果暴力求这个数组的话是 O(n^2)，会超时，所以考虑用树状数组优化，就可以达到 O(n\log n)，原理和树状数组求逆序对一样。

思路

把本题的题面对比下正向康托展开发现式子一模一样，所以也就知道这题中的 S_i 就是 \begin{aligned}\sum_{j=i+1}^n [a_j<a_i]\end{aligned}，所以问题就转化成了已知每个数后面有几个小于自己的数，求这个序列。

这个很好办，用树状数组加二分，我们可以从前往后一个一个确定 a。