如何优化配送员覆盖配送点计数问题的时间复杂度？

问题本质拆解 #

每个配送点(a,b)被覆盖的条件等价于：存在配送员(x,y)满足x≥a且y≥b。我们需要统计每个(a,b)对应的这类配送员的数量，本质是二维平面的右上区域点数查询问题。

优化思路（时间复杂度O((n+m)log(n+m))） #

通过离线处理+排序+树状数组（Fenwick Tree）的组合，将原本O(mn)的查询复杂度降到O(logn)每次。

步骤1：预处理配送员与查询 #

• 把所有配送员的(x,y)按x从大到小排序（x相同时y从大到小排序，不影响核心逻辑）。
• 把所有配送点(a,b)连同其原始索引一起，按a从大到小排序。这样能保证我们处理查询时，所有满足x≥当前a的配送员可以按顺序加入统计结构。

步骤2：坐标离散化 #

由于y的取值范围可能极大（比如1e9），直接用树状数组会浪费空间。我们收集所有配送员的y值和所有配送点的b值，排序去重后给每个值分配一个唯一的索引，将原问题转化为在离散化后的小范围内操作，空间复杂度压缩到O(n+m)。

步骤3：双指针+树状数组统计 #

• 初始化空的树状数组，用一个指针遍历排序后的配送员，另一个指针遍历排序后的查询：
  1. 对于当前查询的(a,b)，先将所有x≥a的配送员的y值插入树状数组（对应离散化索引位置+1）。
  2. 查询树状数组中≥b的y值的总和：这个总和就是当前配送点被覆盖的配送员数量。
  3. 根据原始索引将结果映射回原配送点顺序。

伪代码实现 #

def calculate_coverage(delivery_people, delivery_points):
    # 排序配送员：x降序，x相同则y降序
    delivery_people.sort(key=lambda p: (-p[0], -p[1]))
    # 包装查询并排序：a降序，保留原始索引
    queries = sorted([(a, b, idx) for idx, (a, b) in enumerate(delivery_points)], 
                     key=lambda q: (-q[0], -q[1]))
    
    # 离散化所有y和b的值
    all_y_values = [y for x, y in delivery_people] + [b for a, b, _ in queries]
    sorted_unique = sorted(set(all_y_values))
    y_mapping = {val: idx+1 for idx, val in enumerate(sorted_unique)}  # 树状数组从1开始计数
    max_discrete_idx = len(sorted_unique)

    # 实现树状数组
    class FenwickTree:
        def __init__(self, size):
            self.size = size
            self.tree = [0] * (self.size + 1)
        
        def update(self, idx, delta=1):
            while idx <= self.size:
                self.tree[idx] += delta
                idx += idx & -idx
        
        def query_prefix(self, idx):
            # 查询1到idx的前缀和
            res = 0
            while idx > 0:
                res += self.tree[idx]
                idx -= idx & -idx
            return res

    ft = FenwickTree(max_discrete_idx)
    result = [0] * len(delivery_points)
    dp_ptr = 0  # 配送员遍历指针

    for a, b, original_idx in queries:
        # 加入所有x >= 当前a的配送员
        while dp_ptr < len(delivery_people) and delivery_people[dp_ptr][0] >= a:
            y_val = delivery_people[dp_ptr][1]
            ft.update(y_mapping[y_val])
            dp_ptr += 1
        
        # 计算y >= b的数量：总加入数 - 前缀和(小于b的最大离散索引)
        import bisect
        # 找到第一个>=b的位置，减1就是小于b的最大元素的索引
        pos = bisect.bisect_left(sorted_unique, b)
        if pos == 0:
            # 所有已加入的y都>=b
            count = dp_ptr
        else:
            count = dp_ptr - ft.query_prefix(y_mapping[sorted_unique[pos-1]])
        result[original_idx] = count
    
    return result

复杂度验证 #

• 排序配送员：O(n logn)
• 排序查询：O(m logm)
• 离散化处理：O((n+m) log(n+m))
• 双指针+树状数组操作：每个配送员和查询各执行O(log(n+m))次操作，总复杂度O((n+m) log(n+m))
  整体复杂度完全适配n和m达10^5的场景，效率远高于原有方案。

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