给定两个关联数组A、B，如何高效统计满足A[i]>a且B[i]>b的元素数？

核心思路 #

暴力法的时间复杂度为O(n*q)，在n和q均达到1e5的规模下必然超时，我们可以通过离线处理+离散化+树状数组的方案将复杂度降至O((n+q)log(n+q))，核心逻辑如下：

• 离线处理：不按输入顺序处理查询，将数组配对和查询统一排序后批量处理，避免重复遍历数组
• 离散化：压缩B值和查询b值的取值范围，适配树状数组的索引要求
• 树状数组（Fenwick Tree）：动态维护B值的计数，支持O(logM)时间复杂度的单点更新和前缀和查询，快速统计大于某b值的元素总数

具体实现步骤 #

1. 预处理配对：将所有(A[i], B[i])组合为元组，按A值降序排序
2. 预处理查询：给每个查询加上原始下标，按查询的a值降序排序，保证后续结果能按输入顺序输出
3. 离散化处理：收集所有B[i]和查询中的b值，排序去重后生成值到排名的映射，将可能的大数值压缩到1~2e5的范围
4. 双指针+树状数组统计：
   • 初始化指针指向排序后配对的起始位置，初始化结果数组
   • 遍历每个排序后的查询：
     • 移动指针，将所有A[i] > 当前查询a值的配对的B值插入树状数组
     • 计算树状数组中大于当前查询b值的元素总数，存入结果数组对应原始下标位置
5. 按原始查询顺序输出结果数组

复杂度分析 #

• 排序开销：O(n log n + q log q)
• 离散化开销：O((n+q) log (n+q))
• 树状数组操作：每个元素和查询各执行一次O(log (n+q))的操作，总开销O((n+q) log (n+q))
• 整体复杂度：O((n+q) log (n+q))，可满足1e5规模的时限要求

代码示例（Python） #

class FenwickTree:
    def __init__(self, size):
        self.n = size
        self.tree = [0] * (self.n + 2)  # 防止越界多开2位

    def update(self, idx, delta=1):
        while idx <= self.n:
            self.tree[idx] += delta
            idx += idx & -idx

    def query_prefix(self, idx):
        res = 0
        while idx > 0:
            res += self.tree[idx]
            idx -= idx & -idx
        return res

def solve(A, B, queries):
    # 1. 预处理配对，按A降序排序
    pairs = list(zip(A, B))
    pairs.sort(reverse=True, key=lambda x: x[0])
    # 2. 预处理查询，携带原始下标，按a降序排序
    q_with_idx = [(a, b, idx) for idx, (a, b) in enumerate(queries)]
    q_with_idx.sort(reverse=True, key=lambda x: x[0])
    # 3. 收集所有B值和查询b值做离散化
    all_b = B.copy()
    for _, b, _ in q_with_idx:
        all_b.append(b)
    sorted_unique_b = sorted(list(set(all_b)))
    rank_map = {v: i + 1 for i, v in enumerate(sorted_unique_b)}  # 树状数组从1开始索引
    max_rank = len(sorted_unique_b)
    ft = FenwickTree(max_rank)
    res = [0] * len(queries)
    ptr = 0  # 指向配对数组的指针
    # 4. 遍历查询统计结果
    for a, b, idx in q_with_idx:
        # 插入所有A大于当前a的B值
        while ptr < len(pairs) and pairs[ptr][0] > a:
            b_val = pairs[ptr][1]
            ft.update(rank_map[b_val])
            ptr += 1
        # 大于b的数量 = 总插入数 - 小于等于b的数量
        total_inserted = ptr
        cnt_le_b = ft.query_prefix(rank_map[b])
        res[idx] = total_inserted - cnt_le_b
    return res

# 测试示例
A = [1, 3, 6, 7, 2]
B = [10, 7, 2, 6, 4]
q = [(2, 6), (3, 9), (0, 1)]
print(solve(A, B, q))  # 输出 [1, 0, 5]

内容的提问来源于stack exchange，提问作者Shivanshu Singh