102942: [Atcoder]ABC294 C - Merge Sequences
Description
Score : $300$ points
Problem Statement
You are given strictly increasing sequences of length $N$ and $M$: $A=(A _ 1,A _ 2,\ldots,A _ N)$ and $B=(B _ 1,B _ 2,\ldots,B _ M)$. Here, $A _ i\neq B _ j$ for every $i$ and $j$ $(1\leq i\leq N,1\leq j\leq M)$.
Let $C=(C _ 1,C _ 2,\ldots,C _ {N+M})$ be a strictly increasing sequence of length $N+M$ that results from the following procedure.
- Let $C$ be the concatenation of $A$ and $B$. Formally, let $C _ i=A _ i$ for $i=1,2,\ldots,N$, and $C _ i=B _ {i-N}$ for $i=N+1,N+2,\ldots,N+M$.
- Sort $C$ in ascending order.
For each of $A _ 1,A _ 2,\ldots,A _ N, B _ 1,B _ 2,\ldots,B _ M$, find its position in $C$. More formally, for each $i=1,2,\ldots,N$, find $k$ such that $C _ k=A _ i$, and for each $j=1,2,\ldots,M$, find $k$ such that $C _ k=B _ j$.
Constraints
- $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$ for every $i$ and $j$ $(1\leq i\leq N,1\leq j\leq M)$.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
$N$ $M$ $A _ 1$ $A _ 2$ $\ldots$ $A _ N$ $B _ 1$ $B _ 2$ $\ldots$ $B _ M$
Output
Print the answer in two lines.
The first line should contain the positions of $A _ 1,A _ 2,\ldots,A _ N$ in $C$, with spaces in between.
The second line should contain the positions of $B _ 1,B _ 2,\ldots,B _ M$ in $C$, with spaces in between.
Sample Input 1
4 3 3 14 15 92 6 53 58
Sample Output 1
1 3 4 7 2 5 6
$C$ will be $(3,6,14,15,53,58,92)$. Here, the $1$-st, $3$-rd, $4$-th, $7$-th elements are from $A=(3,14,15,92)$, and the $2$-nd, $5$-th, $6$-th elements are from $B=(6,53,58)$.
Sample Input 2
4 4 1 2 3 4 100 200 300 400
Sample Output 2
1 2 3 4 5 6 7 8
Sample Input 3
8 12 3 4 10 15 17 18 22 30 5 7 11 13 14 16 19 21 23 24 27 28
Sample Output 3
1 2 5 9 11 12 15 20 3 4 6 7 8 10 13 14 16 17 18 19
Input
题意翻译
给定数列 $\{a\}$，$\{b\}$，长度分别为 $n, m$，可得长度 $n+m$ 的数列 $\{c\}$：$c_i=a_i(1\le i\le n), c_i=b_{i-n}(n+1\le i\le n+m)$。求出将 $\{c\}$ 排序后， $\{a\}$ 和 $\{b\}$ 中每个元素在 $\{c\}$ 中的位置。保证 $\forall i\ne j$，均有 $c_i\ne c_j$。$n, m\le 10^5$。Output
问题描述
你有两个长度分别为 $N$ 和 $M$ 的严格递增序列：$A=(A _ 1,A _ 2,\ldots,A _ N)$ 和 $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=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$。
约束
- $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)$。
- 输入中的所有值都是整数。
输入
输入数据从标准输入以以下格式给出：
$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$ 中的位置，用空格分隔。
样例输入 1
4 3 3 14 15 92 6 53 58
样例输出 1
1 3 4 7 2 5 6
$C$ 将为 $(3,6,14,15,53,58,92)$。 在这里，第 $1$ 个、第 $3$ 个、第 $4$ 个和第 $7$ 个元素来自 $A=(3,14,15,92)$，第 $2$ 个、第 $5$ 个和第 $6$ 个元素来自 $B=(6,53,58)$。
样例输入 2
4 4 1 2 3 4 100 200 300 400
样例输出 2
1 2 3 4 5 6 7 8
样例输入 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