「学习笔记」康托展开
至于笔者为什么写这篇学习笔记，其实也没有什么 特殊原因（CantorSort2919
前置芝士：
相信大家都学过 排列组合，我们记 \(P_n^n\) 或 \(A_n^n\) 为 \(1\sim n\) 的 全排列；
并且，全排列还可以按照 字典序 进行排序，
举个栗子，
\(A=\{1,2,3,4\}\)
\(B=\{1,2,3,4,5\}\)
其中 \(len_a
而 康托展开（Cantor Expansion，CE），记录的就是 \(1\sim n\) 全排列的 排名。
正题：
康托展开
让笔者再举一个栗子：
\(A=\{2,5,3,4,1\}\)。
我们知道长为 \(5\) 的排列 \(\{2,5,3,4,1\}\) 大于以 \(1\) 为第一位的 任何排列，以 \(1\) 为第一位的排列有 \(4!\) 种。
非常好理解。
但是对第二位的 \(5\) 而言，它大于 第一位与这个排列相同的，而这一位比 \(5\) 小的 所有排列。
不过我们要注意的是，这一位不仅要比 \(5\) 小，还要满足没有在当前排列的前面出现过，不然统计就重复了。
因此这一位为 \(1,3,4\)，第一位为 \(2\) 的所有排列都比它要小，数量为 \(3\times 3!\)。
按照这样统计下去，答案就是 \(1+4!+3\times 3!+2!+1=46\)。
注意，
我们统计的是排名，因此最前面要 \(+1\)。
注意到我们每次要用到 当前有多少个小于它的数还没有出现，这里可以用 树状数组 统计 比它小的数出现过的次数。
逆康托展开
因为排列的排名和排列是 一一对应 的，所以康托展开满足 双射关系，是 可逆的。可以通过类似上面的过程倒推回来。
如果我们知道一个排列的排名，就可以推出这个排列。
因为 \(4!\) 是严格大于 \(3\times 3!+2\times 2!+1\times 1!\) 的，所以可以认为对于长度为 \(5\) 的排列，排名 \(x\) 除以 \(4!\) 向下取整就是有多少个数小于这个排列的第一位。
用式子来表达，就是第一位记作 \(y\) 时，有：
\[y=\lfloor \frac{x}{4!}\rfloor \]推广，即可得出，\(1\sim n\) 的全排列中，第 \(x\) 名的排列的第一位 \(y\) 的计算式子：
\[y=\lfloor \frac{x}{(n-1)!}\rfloor \]最后的补充：
关于上文提到的 “用树状数组统计比它小的数出现过的次数”，其实也可以用 线段树 来代替。（你想怎样就怎样，不关笔者的事
时间复杂度：\(O(n\log n)\)