版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！

仓库源文，站点原文

title: "题解 - [CodeForces 501 D] Misha and Permutations Summation" categories:

• 算法竞赛
• 题解 tags:
• 算法竞赛
• 题解
• Codeforces
• 数学
• 组合数学
• Cantor展开
• 逆Cantor展开 date: 2020-11-15 00:21:06

题目链接

原始题面

Let's define the sum of two permutations $p$ and $q$ of numbers $0, 1, ..., (n - 1)$ as permutation $\texttt{Perm}((\texttt{Ord}(p)+\texttt{Ord}(q))\bmod n!)$, where $\texttt{Perm}(x)$ is the x-th lexicographically permutation of numbers $0, 1, ..., (n - 1)$ (counting from zero), and $\texttt{Ord}(p)$ is the number of permutation $p$ in the lexicographical order

For example, $\texttt{Perm}(0) = (0, 1, ..., n - 2, n - 1)$, $\texttt{Perm}(n! - 1) = (n - 1, n - 2, ..., 1, 0)$

Misha has two permutations, $p$ and $q$. Your task is to find their sum

Permutation $a = (a_0, a1, ..., a{n - 1})$ is called to be lexicographically smaller than permutation $b = (b_0, b1, ..., b{n - 1})$, if for some k following conditions hold:

$$ a_0 = b_0, a_1 = b1, ..., a{k - 1} = b_{k - 1}, a_k < b_k $$

Input

The first line contains an integer $n$ ($1 ≤ n ≤ 200 000$)

The second line contains n distinct integers from $0$ to $n - 1$, separated by a space, forming permutation $p$

The third line contains n distinct integers from $0$ to $n - 1$, separated by spaces, forming permutation $q$

Output

Print $n$ distinct integers from $0$ to $n - 1$, forming the sum of the given permutations. Separate the numbers by spaces

Examples

Input 1

2
0 1
0 1

Output 1

0 1

Input 2

2
0 1
1 0

Output 2

1 0

Input 3

3
1 2 0
2 1 0

Output 3

1 0 2

Note

Permutations of numbers from $0$ to $1$ in the lexicographical order: $(0, 1), (1, 0)$

In the first sample $\texttt{Ord}(p) = 0$ and $\texttt{Ord}(q) = 0$, so the answer is $\texttt{Perm}((0+0)\bmod 2)=\texttt{Perm}(0)=(0, 1)$

In the second sample $\texttt{Ord}(p) = 0$ and $\texttt{Ord}(q) = 1$, so the answer is $\texttt{Perm}((0+1)\bmod 2)=\texttt{Perm}(1)=(1, 0)$

Permutations of numbers from $0$ to $2$ in the lexicographical order: $(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)$

In the third sample $\texttt{Ord}(p) = 3$ and $\texttt{Ord}(q) = 5$, so the answer is $\texttt{Perm}((3+5)\bmod 6)=\texttt{Perm}(2)=(1, 0, 2)$

题意简述

现在有两个长度为 $n$ 的排列, 由 $0,1,2...n-1$ 这 $n$ 个数字组成

对于一个排列 $p$, $\texttt{Ord}(p)$ 表示 $p$ 是字典序第 $\texttt{Ord}(p)$ 小的排列 (从 $0$ 开始计数)

对于小于 $n!$ 的非负数 $x$, $\texttt{Perm}(x)$ 表示字典序第 $x$ 小的排列

给出两个排列 $p$ 和 $q$, 求 $\texttt{Perm}((\texttt{Ord}(p)+\texttt{Ord}(q))\bmod n!)$

from https://www.luogu.com.cn/discuss/show/188178

解题思路

显然是 Cantor 展开和逆 Cantor 展开的模板题

但这题的 $n$ 是 2e5 的, 我们肯定不能直接套板子

注意到 $d(A)=P_Af_n^T$, 对于给出的 $p,q$, 我们可以考虑直接将 $P_p,P_q$ 相加并还原即可

另外注意在 CF 的评测环境是 32 位的, 即std::size_t是unsigned int而不是uint64_t

复杂度

$O(n\log n)$

代码参考