小O的子序列最值(二)

[题目链接](https://www.nowcoder.com/practice/ccde5aaa096f418b81ee6ed9dc253504)

题意

给定两个长度为 $n$ 的数组 $A$ 和 $B$ ，从 $A$ 和 $B$ 中各选一个非空子序列，要求 $A$ 所选子序列的最大值不大于 $B$ 所选子序列的最小值。求满足条件的选法总数，答案对 $10^9+7$ 取模。

思路

枚举最大值分组

将两个数组分别排序。

对于从 $A$ 中选取的子序列，其最大值是确定的。我们可以枚举 $A$ 中每个不同的值 $v$ 作为所选子序列的最大值，然后对每个 $v$ ：

统计从 $A$ 中选出最大值恰好为 $v$ 的非空子序列数。
统计从 $B$ 中选出最小值 $\geq v$ 的非空子序列数。

两者相乘即为以 $v$ 为界的贡献，所有 $v$ 的贡献求和即为答案。

计数公式

设排序后的 $A$ 中，值 $v$ 首次出现位置为 $lo$ ，末次出现位置为 $hi$ （0-indexed）。

A 中最大值恰好为 $v$ 的非空子序列数：

必须从 $A[lo..hi]$ （所有等于 $v$ 的元素）中至少选 1 个：共 $2^{hi-lo+1} - 1$ 种。
$A[0..lo-1]$ 中所有元素均小于 $v$ ，可以任意选取：共 $2^{lo}$ 种。
合计： $2^{lo} \times (2^{hi-lo+1} - 1)$

B 中最小值 $\geq v$ 的非空子序列数：

设 $B$ 中 $\geq v$ 的元素个数为 $c_b$ （用二分查找得到）。
从这 $c_b$ 个元素中选至少 1 个： $2^{c_b} - 1$ 。

复杂度

排序 $O(n \log n)$ ，枚举每个不同值并二分查找 $O(n \log n)$ ，预处理 2 的幂次 $O(n)$ 。总体 $O(n \log n)$ 。

示例验证

输入：

2
1 2
3 4

排序后 $A = [1, 2]$ ， $B = [3, 4]$ 。

$v = 1$ （ $lo=0, hi=0$ ）：countA = $2^0 \times (2^1 - 1) = 1 \times 1 = 1$ ； $B$ 中 $\geq 1$ 的有 2 个，countB = $2^2 - 1 = 3$ ；贡献 $1 \times 3 = 3$ 。
$v = 2$ （ $lo=1, hi=1$ ）：countA = $2^1 \times (2^1 - 1) = 2 \times 1 = 2$ ； $B$ 中 $\geq 2$ 的有 2 个，countB = $2^2 - 1 = 3$ ；贡献 $2 \times 3 = 6$ 。

总答案 = $3 + 6 = 9$ ，与期望一致。

代码

C++

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<int> 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());

    vector<long long> pw(n + 1);
    pw[0] = 1;
    for (int i = 1; i <= n; i++) pw[i] = pw[i-1] * 2 % MOD;

    long long ans = 0;
    int i = 0;
    while (i < n) {
        int j = i;
        while (j < n && a[j] == a[i]) j++;
        int v = a[i];
        int lo = i, hi = j - 1;
        long long countA = pw[lo] * ((pw[hi - lo + 1] - 1 + MOD) % MOD) % MOD;
        int cb = n - (int)(lower_bound(b.begin(), b.end(), v) - b.begin());
        long long countB = (pw[cb] - 1 + MOD) % MOD;
        ans = (ans + countA * countB) % MOD;
        i = j;
    }

    cout << ans << endl;
    return 0;
}

Java

import java.util.*;
import java.io.*;

public class Main {
    static final long MOD = 1_000_000_007L;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());

        int[] a = new int[n], b = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) a[i] = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) b[i] = Integer.parseInt(st.nextToken());

        Arrays.sort(a);
        Arrays.sort(b);

        long[] pw = new long[n + 1];
        pw[0] = 1;
        for (int i = 1; i <= n; i++) pw[i] = pw[i-1] * 2 % MOD;

        long ans = 0;
        int i = 0;
        while (i < n) {
            int j = i;
            while (j < n && a[j] == a[i]) j++;
            int v = a[i];
            int lo = i, hi = j - 1;
            long countA = pw[lo] * ((pw[hi - lo + 1] - 1 + MOD) % MOD) % MOD;
            int lb = lowerBound(b, v);
            int cb = n - lb;
            long countB = (pw[cb] - 1 + MOD) % MOD;
            ans = (ans + countA * countB) % MOD;
            i = j;
        }

        System.out.println(ans);
    }

    static int lowerBound(int[] arr, int val) {
        int lo = 0, hi = arr.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (arr[mid] < val) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }
}