AT_abc294_c [ABC294C] Merge Sequences

题目描述

给定一个长度为 $N$ 的严格单调递增序列 $A=(A_1,A_2,\ldots,A_N)$ 和一个长度为 $M$ 的严格单调递增序列 $B=(B_1,B_2,\ldots,B_M)$。这里，对于所有的 $i,j\ (1\leq i\leq N,1\leq j\leq M)$，都有 $A_i\neq B_j$。

定义长度为 $N+M$ 的严格单调递增序列 $C=(C_1,C_2,\ldots,C_{N+M})$，其获得方式如下：

• 首先，将 $A$ 和 $B$ 连接成一个序列 $C$。具体来说，对于 $i=1,2,\ldots,N$，令 $C_i=A_i$，对于 $i=N+1,N+2,\ldots,N+M$，令 $C_i=B_{i-N}$。
• 然后，将 $C$ 按升序排序。

请你求出 $A_1,A_2,\ldots,A_N$ 和 $B_1,B_2,\ldots,B_M$ 在 $C$ 中分别是第几位。更严格地说，先依次求出对于 $i=1,2,\ldots,N$，满足 $C_k=A_i$ 的 $k$，再依次求出对于 $j=1,2,\ldots,M$，满足 $C_k=B_j$ 的 $k$。

输入格式

输入以如下格式从标准输入读入。

$N$ $M$ $A_1$ $A_2$ $\ldots$ $A_N$ $B_1$ $B_2$ $\ldots$ $B_M$

输出格式

请输出 $2$ 行。
第 $1$ 行输出 $A_1,A_2,\ldots,A_N$ 在 $C$ 中分别是第几位，数之间用空格隔开。
第 $2$ 行输出 $B_1,B_2,\ldots,B_M$ 在 $C$ 中分别是第几位，数之间用空格隔开。

输入输出样例 #1

输入 #1

4 3
3 14 15 92
6 53 58

输出 #1

1 3 4 7
2 5 6

输入输出样例 #2

输入 #2

4 4
1 2 3 4
100 200 300 400

输出 #2

1 2 3 4
5 6 7 8

输入输出样例 #3

输入 #3

8 12
3 4 10 15 17 18 22 30
5 7 11 13 14 16 19 21 23 24 27 28

输出 #3

1 2 5 9 11 12 15 20
3 4 6 7 8 10 13 14 16 17 18 19

说明/提示

限制条件

• $1\leq N,M\leq 10^5$
• $1\leq A_1<A_2<\cdots<A_N\leq 10^9$
• $1\leq B_1<B_2<\cdots<B_M\leq 10^9$
• 对于所有 $i,j\ (1\leq i\leq N,1\leq j\leq M)$，都有 $A_i\neq B_j$
• 输入均为整数

样例解释 1

$C$ 为 $(3,6,14,15,53,58,92)$。$A=(3,14,15,92)$ 的元素分别在第 $1,3,4,7$ 位，$B=(6,53,58)$ 的元素分别在第 $2,5,6$ 位。

由 ChatGPT 4.1 翻译