小O的子序列最值(二)
小O的子序列最值(二)
OPPO 笔试真题 · 2024 秋招 · 移动开发
判题请到牛客原题提交。
题目描述
小O有两个长度为 的数组，现在她想从这两个数组中分别选出一个非空子序列，使得从第一个数组中选出的子序列的最大值不大于从第二个数组中选出的子序列的最小值。
小红想知道有多少种选取方法。
如果数组 可以通过删除数组 中的若干（可能为零或全部）元素得到，则数组 是数组 的子序列。
输入格式
第一行输入一个整数 代表数组的长度。
第二行输入 个整数 代表第一个数组。
第三行输入 个整数 代表第二个数组。
输出格式
在一行上输出一个整数，表示答案对 取模的结果。
示例
示例 1
输入：
2
1 2
3 4输出：
9说明：
第一个数组选取任意非空子序列，第二个数组选取任意非空子序列，共 9 种选法。
解题思路
第一步：理解问题本质
和《小O的子序列最值》一样，子序列的最大值、最小值只取决于「选了哪些下标」，
所以这里数的是下标集合对的个数：
求非空集合
A ⊆ {1..n}与非空集合B ⊆ {1..n}的组数，使得max(a[A]) <= min(b[B])。
设 A 的最大值恰好为 x、B 的最小值恰好为 y，条件就是 x <= y。于是
答案 = Σ_{x <= y} cnt_a[x] * cnt_b[y]其中 cnt_a[x] 是「最大值恰好为 x」的非空子集数，cnt_b[y] 是「最小值恰好为 y」的
非空子集数。两边的计数互相独立，先各自算好，再按 x <= y 合并。
第二步：暴力解法（为什么不能用）
直接枚举两边的下标集合是 O(4^n)；就算先按值分类，枚举所有 (x, y) 值对也是O(n^2)，n = 10^5 时是 10^10 次运算。需要一种「一边扫一边累加」的办法。
第三步：怎么数「最大值恰好为 v」的非空子集
把 a 中等于 v 的位置数出来，记为 k；小于 v 的位置数记为 c。想要最大值恰好是 v，
必须「至少选一个等于 v 的元素」（否则最大值就小于 v 了），而更小的 c 个元素
可以随便选或不选。所以
cnt_a[v] = (2^k - 1) * 2^c同理，对 b 来说「最小值恰好为 v」要求至少选一个等于 v 的元素，
而比 v 大的元素可以随便选：
cnt_b[v] = (2^k - 1) * 2^c'这里 c' 是 b 中严格大于 v 的元素个数。
第四步：合并成一趟扫描
把两个数组出现过的所有取值合并、升序扫描。扫描到 v 时：
- 先把
cnt_a[v]累加进「最大值<= v的 a 子集总数」这个前缀和cum_a； - 再用
cnt_b[v] * cum_a累加进答案。
因为此时 cum_a 里装的全是 x <= v 的方案，正好满足 x <= y。
每个取值只处理一次，合并部分是 O(n)。
细节：2^c 与 2^c' 都要对 1e9+7 取模，指数表预处理到 n。
完整代码实现
import sys
from collections import Counter
MOD = 10 ** 9 + 7
def solve() -> None:
"""按「最大值 / 最小值」分类计数，再用前缀和合并"""
data = sys.stdin.buffer.read().split()
if not data:
return
n = int(data[0])
a = list(map(int, data[1:1 + n]))
b = list(map(int, data[1 + n:1 + 2 * n]))
# 2 的幂表：2^0 .. 2^n
pow2 = [1] * (n + 1)
for i in range(1, n + 1):
pow2[i] = pow2[i - 1] * 2 % MOD
ca = Counter(a)
cb = Counter(b)
ans = 0
cum_a = 0 # 最大值 <= 当前值的 a 非空子集总数
less_a = 0 # 已经扫过的 a 元素个数（都严格小于当前值）
b_le = 0 # 已经扫过的 b 元素个数（都 <= 当前值）
for v in sorted(set(a) | set(b)):
ka = ca.get(v, 0)
kb = cb.get(v, 0)
b_le += kb
if ka:
# 最大值恰为 v：至少选一个 v，更小的元素任选
ways_a = (pow2[ka] - 1) * pow2[less_a] % MOD
cum_a = (cum_a + ways_a) % MOD
less_a += ka
if kb:
# 最小值恰为 v：至少选一个 v，更大的元素任选
greater_b = n - b_le
ways_b = (pow2[kb] - 1) * pow2[greater_b] % MOD
ans = (ans + ways_b * cum_a) % MOD
sys.stdout.write(str(ans) + "\n")
if __name__ == "__main__":
solve()示例推演
推演一：题面样例 a = [1,2]、b = [3,4]
先算分类计数：
| 项 | 计算 | 值 |
|---|---|---|
cnt_a[1] | (2^1 - 1) * 2^0 | 1 |
cnt_a[2] | (2^1 - 1) * 2^1（更小的 1 可选） | 2 |
cnt_b[3] | (2^1 - 1) * 2^1（更大的 4 可选） | 2 |
cnt_b[4] | (2^1 - 1) * 2^0 | 1 |
再升序扫描：
| v | cum_a | cnt_b[v] | 本次贡献 | 累计答案 |
|---|---|---|---|---|
| 1 | 1 | 0 | 0 | 0 |
| 2 | 3 | 0 | 0 | 0 |
| 3 | 3 | 2 | 2 * 3 = 6 | 6 |
| 4 | 3 | 1 | 1 * 3 = 3 | 9 |
答案 9，与题面一致：a 的任意非空子序列最大值都不超过 2，
b 的任意非空子序列最小值都不小于 3，3 * 3 = 9 种组合全部合法。
推演二：a = [2,1]、b = [1,2]
| 项 | 值 |
|---|---|
cnt_a[1] | 1 |
cnt_a[2] | 2 |
cnt_b[1] | 2（更大的 2 可选） |
cnt_b[2] | 1 |
扫描：v = 1 时 cum_a = 1，cnt_b[1] = 2，贡献 2；v = 2 时 cum_a = 1 + 2 = 3，cnt_b[2] = 1，贡献 3。答案 5。
手工核对：A = {1}（a 的第 2 个元素）时 3 种 B 都合法；A = {2} 时只有 B = {2} 合法；A = {2,1} 时同样只有 B = {2} 合法，共 3 + 1 + 1 = 5 种。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 枚举两边的下标集合 | O(4^n) | O(n) | 只能验证 n <= 10 的小数据 |
| 分类计数 + 按值二维枚举 | O(n^2) | O(n) | n = 10^5 时约 10^10 次，超时 |
| 分类计数 + 升序扫描前缀和 | O(n log n) | O(n) | 推荐，排序是唯一的对数项 |
易错点总结
1. 忘记「至少选一个等于 v 的元素」
2^k 里包含了「一个都不选」的情况，必须减 1。写成 2^k 会把「最大值小于 v」
的方案重复算到 cnt_a[v] 里，答案偏大。
2. 严格小于 / 严格大于的方向搞反
cnt_a[v] 里可自由选择的是小于 v 的元素；cnt_b[v] 里可自由选择的是大于 v
的元素。两个方向是相反的，这一点写反了样例就会对不上。
3. 合并顺序写错
必须先用 cnt_a[v] 更新 cum_a、再乘 cnt_b[v]，这样 cum_a 里包含的是x <= v（含等于）。若先乘后更新，会漏掉 x == y 这一批方案。
4. greater_b 的算法
greater_b = n - b_le，其中 b_le 是「扫描到 v 为止（含 v）的 b 元素个数」。b_le 要在处理 v 时先加上 kb，否则把等于 v 的元素也算成「大于 v」了。
5. 取模
pow2、两个乘积、累加都要取模。本题不取模的话，子集数量会达到 2^n 的量级
（n = 10^5 时是十万位的大数），既慢又不是题目要的答案。
扩展思考
- 把条件改成严格小于（
x < y），只需把「先更新cum_a再乘」改成「先乘再更新」，
就自动排除了x == y的方案。 - 若要求两个子序列长度相同，计数时需要额外记录长度维度，可以用生成函数或
二维 DP 处理。 - 这一类「按最值分类 + 前缀和合并」的技巧，在统计区间最值关系的题目里非常常见，
例如统计「左边最大值不超过右边最小值」的划分方案数。