codeforces 501 D Misha and Permutations Summation (康托展开+康托逆展开+factorial_number_system+线段树×2)

题目链接

题意:给出两个排列,定义ord(p)为排列p的顺序(字典顺从小到大),定义perm(x)为顺序为x的排列,现在要求 1 ≤ n ≤ 200 000

 

思路:首先去学了一下康托展开和逆展开。。。其实就是对于这种排列之类的问题。。。的一个比较省空间的hash函数。。。?

康托展开资料

然后由于n非常大。。康托展开中要查找当前位置后面有多少个比当前位置小的。。。

screenshot-from-2016-09-14-14-48-25

然而这复杂是n2。。。肯定gg。。。

因此里面那层我们用一课线段树维护。。。复杂度nlgn

在康托逆展开的过程中。。。我们要查询之前没有出现过的第k个元素。。。。

因为n很大这里也需要线段树来维护。。。

所以再建一棵线段树。。。某位置表示初始时刻是否为空,初始都为1,表示都没有出现。思想类似于poj 2828
poj 2828解题报告

 

然后还是由于n很大。。。在康托展开中的阶乘部分。。。完全存不下。。。

直接用高精度应该也能做?

不过比较推荐的做法是:
The Factorial Number System
wiki_Factorial number system

是一种和阶乘相关的进制表示法。

大概就是不同位置上的权值,不像一般的k进制数,是k^0,k^1,k^2….

而是0!,1!,2!。。。

这种表示合法的正确性基于:

具体参见上面两个链接。

 

因为我们可以把所有康托展开都用 Factorial number system来表示。