题目链接 题意：给出两个排列，定义ord(p)为排列p的顺序（字典顺从小到大），定义perm(x)为顺序为x的排列，现在要求 1 ≤ n ≤ 200 000 思路：首先去学了一下康托展开和逆展开。。。其实就是对于这种排列之类的问题。。。的一个比较省空间的hash函数。。。？ 康托展开资料 然后由于n非常大。。康托展开中要查找当前位置后面有多少个比当前位置小的。。。 然而这复杂是n2。。。肯定gg。。。 因此里面那层我们用一课线段树维护。。。复杂度nlgn 在康托逆展开的过程中。。。我们要查询之前没有出现过的第k个元素。。。。 因为n很大这里也需要线段树来维护。。。 所以再建一棵线段树。。。某位置表示初始时刻是否为空，初始都为1，表 …

感觉就是为了记录排列。。。重复之类的。。。用到的一个hash函数。。。？ 维基百科 讲解