题解 | 小O的子序列最值(二)

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;

int main() {
    int n; 
    cin >> n;
    vector<long long> a(n), b(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n; ++i) cin >> b[i];
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    // 预计算 2^k
    vector<long long> p2(n + 1, 1);
    for (int i = 1; i <= n; ++i) p2[i] = (p2[i-1] * 2) % MOD;
    long long ans = 0;
    for (int j = 0; j < n; ++j) {
        int cnt = upper_bound(a.begin(), a.end(), b[j]) - a.begin(); // a 中 ≤ b[j] 的个数
        if (cnt == 0) continue;                                      // A 必须非空
        long long waysA = (p2[cnt] - 1 + MOD) % MOD;                 // 非空
        long long waysB = p2[n - j - 1];                             // 选定最小值为 b[j]
        ans = (ans + waysA * waysB) % MOD;
    }

    cout << ans % MOD << '\n';
    return 0;
}