One can find \(C=(C _ 1,C _ 2,\ldots,C _ {N+M})\) in an \(O((N+M)\log(N+M))\) by concatenating the sequences into one and sorting it. While this is fast enough, one can also find \(C\) even faster.

Once you obtained actual \(C\), one can find \(i\) from \(C _ i\) in an \(O(\log(N+M))\) or expected \(O(1)\) time (with a proper precomputation). The former complexity can be achieved by a binary search or an associated array (using a balanced binary search tree etc.), and the other by an associated array (using hash map etc.)

Thus, the problem has been solved in a total of \(O((N+M)\log(N+M))\) or expected \(O(N+M)\) time.

One can also solved this problem in at worst a total of \(O(N+M)\) time by finding the answer while merging or supplying appropriate values before merging.

Sample codes follow.

• Solution in python

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

C = sorted(A + B)

get_index = {c: i + 1 for i, c in enumerate(C)}

for a in A:
    print(get_index[a])

for b in B:
    print(get_index[b])

• Solution in C++, time complexity \(O((N+M)\log(N+M))\)

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    using namespace std;

    unsigned N, M;
    cin >> N >> M;

    vector<unsigned> A(N), B(M);
    for (auto &&a : A) cin >> a;
    for (auto &&b : B) cin >> b;

    vector<unsigned> C(N + M);
    merge(begin(A), end(A), begin(B), end(B), begin(C));

    for (const auto a : A)
        cout << lower_bound(begin(C), end(C), a) - begin(C) + 1 << " ";
    cout << endl;

    for (const auto b : B)
        cout << lower_bound(begin(C), end(C), b) - begin(C) + 1 << " ";
    cout << endl;

    return 0;
}

• Solution in C++, time complexity \(O(N+M)\) at worst

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

int main() {
    using namespace std;

    unsigned N, M;
    cin >> N >> M;

    vector<pair<unsigned, unsigned>> A(N), B(M);
    for (auto&&[a, _] : A) cin >> a;
    for (auto&&[b, _] : B) cin >> b;
    for (unsigned i{}; i < N; ++i) A[i].second = i;
    for (unsigned i{}; i < M; ++i) B[i].second = i + N;

    vector<pair<unsigned, unsigned>> C(N + M);
    merge(begin(A), end(A), begin(B), end(B), begin(C));

    vector<unsigned> ans(N + M);
    for (unsigned i{}; i < N + M; ++i) ans[C[i].second] = i;

    for (unsigned i{}; i < N + M; ++i) cout << ans[i] + 1 << " ";

    return 0;
}