給定兩個 非嚴格遞增 的整數陣列 $L$ 與 $R$，請將它們合併為一個 非嚴格遞增 的新陣列 $\text{arr}$。

你需要實作一個函式 merge，將合併後的結果放入陣列 $\text{arr}$ 中。

• 請注意，你的 merge 函式應在 線性時間 $O(n)$ 內完成（其中 $n = n_1 + n_2$）。
  使用 std::sort 等一般排序函式將會發生 TLE。

使用範例程式碼

評測時，你所實作的 merge 函式會被放入以下程式碼中進行測試：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void merge(vector<int> &arr, vector<int> &L, vector<int> &R){
    // TODO
}

int main(){

    // input
    int n1, n2;
    int x1, a1, b1, x2, a2, b2;
    const int MOD = 1e9;

    cin >> n1 >> n2;
    cin >> x1 >> a1 >> b1 >> x2 >> a2 >> b2;
    vector<int> L(n1), R(n2);

    L[0] = x1;
    for (int i = 1; i < n1; i++) {
        L[i] = (1LL * L[i-1] * a1 + b1) % MOD + 1;
    }
    sort(L.begin(), L.end());

    R[0] = x2;
    for (int i = 1; i < n2; i++) {
        R[i] = (1LL * R[i-1] * a2 + b2) % MOD + 1;
    }
    sort(R.begin(), R.end());

    // process
    vector<int> arr(n1 + n2);
    merge(arr, L, R);

    // output
    int output = 0;
    for (int i = 0; i < n1 + n2; i++) {
        output ^= (i + arr[i]);
    }
    cout << output << "\n";

    return 0;
}

上傳說明

請上傳你實作的 merge 函式，並包含需要使用的標頭檔與命名空間，例如：

#include <...>
using namespace ...;

void merge(vector<int> &arr, vector<int> &L, vector<int> &R){
    // TODO
}