#184. 单位蒙日矩阵乘法

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB 通过: 103 | 提交: 154

题目描述

对于一个长度为 $n$ 的排列 $a$ ，定义 $f(a)$ 为一个 $n+1$ 阶方阵，其中 $f(a)_{i,j} = \sum_{i' \ge i} [a_{i'} < j]$ 。（排列的下标、矩阵的下标、排列的值域均从 1 开始记）

对于两个矩阵 $A, B$ ，定义其距离乘法 $A \otimes B$ ，其中 $(A \otimes B)_{i,j} = \min_k (A_{i,k} + B_{k,j})$ 。

给定两个长度为 $n$ 的排列 $a, b$ ，可以证明存在唯一的长度为 $n$ 的排列 $c$ ，使得 $f(a) \otimes f(b) = f(c)$ ，请输出 $c$ 。

第一行，一个正整数 $n$ 。

接下来两行，各 $n$ 个正整数，分别代表排列 $a, b$ 。

一行， $n$ 个正整数，代表排列 $c$ 。

输入

3
1 3 2
2 1 3

输出

2 3 1

对于 30% 的数据， $n \le 100$ ；

对于 100% 的数据， $1 \le n \le 5 \times 10^5$ ，保证 $a, b$ 是排列。