📝 题目大意

给定两个严格递增且元素互不相同的序列 $A$（长度 $N$）和 $B$（长度 $M$），将它们合并后排序得到序列 $C$（长度 $N+M$）。要求输出 $A$ 中每个元素在 $C$ 中的位置（1-indexed），以及 $B$ 中每个元素在 $C$ 中的位置。

💡 解题思路

1. 题目分析：$N, M \leq 10^5$，$A_i, B_i \leq 10^9$。$A$ 和 $B$ 各自严格递增且两两不同，因此 $C$ 就是 $A$ 和 $B$ 归并后的序列。本质上是求两个有序序列的归并过程中每个元素的排名。

2. 算法推导：使用双指针归并，模拟归并排序的过程。

   • 定义指针 i（遍历 $A$，从 $1$ 开始）、j（遍历 $B$，从 $1$ 开始）、k（当前归并到的位置，从 $1$ 开始）。
   • 数组 c[i] 记录 $A_i$ 在 $C$ 中的位置，数组 d[j] 记录 $B_j$ 在 $C$ 中的位置。
   • 当 i <= n 且 j <= m 时，比较 a[i] 和 b[j]：
     • 若 a[i] < b[j]，则 c[i] = k，i++，k++。
     • 否则，d[j] = k，j++，k++。
   • 循环结束后，将剩余元素（全部来自 $A$ 或全部来自 $B$）依次赋予位置 k。
   • 最终按顺序输出 c[1..n] 和 d[1..m]。

3. 边界与细节：

   • 由于 $A$ 和 $B$ 各自严格递增，双指针归并不会有重复值问题。
   • 当某一序列先耗尽时，需要将另一序列的剩余部分一次性处理完。
   • 输出两行，每行末尾有空格不影响评测（AtCoder 一般允许行末空格）。

⏱️ 复杂度分析

• 时间复杂度：$O(N + M)$，每个元素仅被访问一次。
• 空间复杂度：$O(N + M)$，存储 $A$、$B$ 以及位置数组 $c$、$d$。

💻 标准代码 (C++)

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;
int n, m, a[N], b[N], c[N], d[N];

signed main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];  // 读入序列 A
    for (int i = 1; i <= m; i++) cin >> b[i];  // 读入序列 B

    int i = 1, j = 1, k = 1;  // i 遍历 A, j 遍历 B, k 为当前归并位置
    while (i <= n && j <= m)
    {
        if (a[i] < b[j])       // A 当前元素更小，先归入 C
        {
            c[i] = k;          // 记录 A[i] 在 C 中的位置
            i++, k++;
        }
        else                   // B 当前元素更小，先归入 C
        {
            d[j] = k;          // 记录 B[j] 在 C 中的位置
            j++, k++;
        }
    }
    while (i <= n)             // A 剩余部分依次归入
    {
        c[i] = k;
        i++, k++;
    }
    while (j <= m)             // B 剩余部分依次归入
    {
        d[j] = k;
        j++, k++;
    }

    for (int i = 1; i <= n; i++) cout << c[i] << ' ';  // 输出 A 各元素的位置
    cout << endl;
    for (int i = 1; i <= m; i++) cout << d[i] << ' ';  // 输出 B 各元素的位置
    cout << endl;
    return 0;
}