合并序列。有两个长度为N的单调不降序列A和B，序列的每个元素都是小于109的非负整数。在A和B中各取一个数相加可以得到N2个和，求其中第k小的和。上述参数满足N≤105和1≤K≤N2。-万卷网

题型：组合题

合并序列。有两个长度为N的单调不降序列A和B，序列的每个元素都是小于109的非负整数。在A和B中各取一个数相加可以得到N2个和，求其中第k小的和。上述参数满足N≤105和1≤K≤N2。

#include <iostream>
using namespace std;

const int maxn = 100005;

int n;
long long k;
int a[maxn], b[maxn];

int *upper_bound(int *a, int *an, int ai) {
    int l = 0, r = ( ① );
    while (l < r) {
        int mid = (l + r) >> 1;
        if (②) {
            r = mid;
        }
        else {
            l = mid + 1;
        }
    }
    return ( ③ );
}

long long get_rank(int sum) {
    long long rank = 0;
    for (int i = 0; i < n; i++) {
        rank += upper_bound(b, b + n, sum - a[i]) - b;
    }
    return rank;
}

int solve() {
    int l = 0, r =（ ④ ）;
    while (l < r) {
        int mid = ((long long)l + r) >> 1;
        if  ( ⑤ ） {
            l = mid + 1;
        }
        else {
            r = mid;
        }
    }
    return l;
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
        cin >> b[i];
    cout << solve() << endl;
    return 0;
}

(1)．

②处应填（）