Merge Sequences

题目描述

你被给予长度为 $N$ 和 $M$ 的严格递增序列：$A=(A _ 1,A _ 2,\ldots,A _ N)$ 和 $B=(B _ 1,B _ 2,\ldots,B _ M)$。 这里对每个 $i$ 和 $j$ 都有 $A _ i\neq B _ j$ $(1\leq i\leq N,1\leq j\leq M)$。 令 $C=(C _ 1,C _ 2,\ldots,C _ {N+M})$ 为长度为 $N+M$ 的严格递增序列，该序列由以下过程得到。

令 $C$ 为 $A$ 和 $B$ 的连接。形式上，令 $C _ i=A _ i$ 对于 $i=1,2,\ldots,N$，并且 $C _ i=B _ {i-N}$ 对于 $i=N+1,N+2,\ldots,N+M$。 将 $C$ 按升序排序。

对于每个 $A _ 1,A _ 2,\ldots,A _ N, B _ 1,B _ 2,\ldots,B _ M$，找出它在 $C$ 中的位置。 更形式地，对于每个 $i=1,2,\ldots,N$，找出 $k$ 使得 $C _ k=A _ i$，并且对于每个 $j=1,2,\ldots,M$，找出 $k$ 使得 $C _ k=B _ j$。

输入格式

输入从标准输入按以下格式给出： $N$ $M$ $A _ 1$ $A _ 2$ $\ldots$ $A _ N$ $B _ 1$ $B _ 2$ $\ldots$ $B _ M$

输出格式

以两行打印答案。
第一行应包含 $A _ 1,A _ 2,\ldots,A _ N$ 在 $C$ 中的位置，位置之间用空格分隔。
第二行应包含 $B _ 1,B _ 2,\ldots,B _ M$ 在 $C$ 中的位置，位置之间用空格分隔。

4 3
3 14 15 92
6 53 58

1 3 4 7
2 5 6

4 4
1 2 3 4
100 200 300 400

1 2 3 4
5 6 7 8

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

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\lt A _ 2\lt\cdots\lt A _ N\leq 10^9$ $1\leq B _ 1\lt B _ 2\lt\cdots\lt B _ M\leq 10^9$ $A _ i\neq B _ j$ 对于每个 $i$ 和 $j$ $(1\leq i\leq N,1\leq j\leq M)$。 输入中的所有值均为整数。$C$ 将是 $(3,6,14,15,53,58,92)$。 在这里，第 $1$ 个、第 $3$ 个、第 $4$ 个、第 $7$ 个元素来自 $A=(3,14,15,92)$，第 $2$ 个、第 $5$ 个、第 $6$ 个元素来自 $B=(6,53,58)$。

标签: AtCoder|abc294C

来源

AtCoder|abc294C