算法
(排序) $O((n+m)\log (n+m))$
可以对序列 $\{(A_0, 0), ~(A_1, 1), ~\cdots, ~(A_{n-1}, n-1), (B_0, n), (B_1, n+1), \cdots, (B_{m-1}, n+m-1)\}$ 进行排序
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using P = pair<int, int>;
int main() {
int n, m;
cin >> n >> m;
vector<int> a(n), b(m);
rep(i, n) cin >> a[i];
rep(i, m) cin >> b[i];
vector<P> c;
rep(i, n) c.emplace_back(a[i], i);
rep(i, m) c.emplace_back(b[i], n+i);
sort(c.begin(), c.end());
vector<int> ai(n), bi(m);
rep(i, n+m) {
int j = c[i].second;
if (j < n) ai[j] = i+1;
else bi[j-n] = i+1;
}
rep(i, n) cout << ai[i] << " \n"[i == n-1];
rep(i, m) cout << bi[i] << " \n"[i == m-1];
return 0;
}
算法2
(二路归并) $O(n+m)$
可以调用 std::inplace_merge
对 $(A_i, i)$ 和 $(B_i, i)$ 按从小到大的顺序进行合并
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using P = pair<int, int>;
int main() {
int n, m;
cin >> n >> m;
vector<P> c(n+m);
rep(i, n+m) {
cin >> c[i].first;
c[i].second = i;
}
inplace_merge(c.begin(), c.begin()+n, c.end());
vector<int> ans(n+m);
rep(i, n+m) ans[c[i].second] = i+1;
rep(i, n+m) cout << ans[i] << ' ';
return 0;
}