357区间和匹配问题

问题描述

小 U 手上有两个长度为 n 的数组 A 和 B。她需要找到所有的区间[L, R]，满足在这个区间内，数组 A 的元素和在范围[La, Ra]之间，同时数组 B 的元素和在范围[Lb, Rb]之间。你能帮助她计算满足条件的区间数量吗？

解题思路

1. 前缀和预处理

   • 使用前缀和数组 SA 和 SB 分别存储数组 A 和 B 的累积和

2. 二分查找

   • 遍历每个右端点 i
   • 对于每个右端点，需要找到合适的左端点范围
   • 使用二分查找快速定位满足条件的左端点区间

3. 区间条件转换

   • 对于区间[L,R]，其和必须在[La,Ra]之间
   • 可以转换为: SA[R] - SA[L-1] ∈ [La,Ra]
   • 进一步转换为: SA[R] - Ra ≤ SA[L-1] ≤ SA[R] - La

def solution(N: int, A: list, B: list, La: int, Ra: int, Lb: int, Rb: int) -> int:
    # 计算前缀和数组
    SA = list(accumulate(A, initial=0))  # A的前缀和
    SB = list(accumulate(B, initial=0))  # B的前缀和
    res = 0

    # 遍历每个右端点
    for i in range(1, len(A) + 1):
        # 对数组A，计算左端点应满足的值域范围
        x, y = SA[i] - La, SA[i] - Ra  # y <= SA[L-1] <= x
        l1, r1 = bisect_left(SA, y), bisect_right(SA, x)

        # 对数组B，计算左端点应满足的值域范围
        x, y = SB[i] - Lb, SB[i] - Rb  # y <= SB[L-1] <= x
        l2, r2 = bisect_left(SB, y), bisect_right(SB, x)

        # 取两个数组共同满足的左端点范围
        l = max(l1, l2)  # 左端点的最大值
        r = min(r1, r2)  # 右端点的最小值
        res += max(0, r - l)  # 累加满足条件的区间数

    return res

复杂度分析

• 时间复杂度：O(N log N)
  • 前缀和计算：O(N)
  • 对每个右端点进行二分查找：O(N log N)
• 空间复杂度：O(N)
  • 需要存储两个前缀和数组