Custom Comparators and Coordinate Compression 自定义比较器和坐标压缩

Custom Comparators and Coordinate Compression

自定义比较器和坐标压缩

本文介绍两种在竞赛编程中常用的技术：自定义排序和坐标压缩。

---

一、自定义排序

排序不仅限于数字，还可以用于任意对象。

方法一：使用元组

将对象与排序关键字打包成元组：

edge_num = 4
edges = []
for _ in range(edge_num):
    a, b, width = [int(i) for i in input().split()]
    edges.append((width, a, b))  # (关键字, 其他数据)
edges.sort()  # 按 width 升序排序

for e in edges:
    print(f"({e[1]}, {e[2]}): {e[0]}")

方法二：Key 函数

使用 key 参数指定排序依据：

class Edge:
    def __init__(self, a: int, b: int, width: int):
        self.a = a
        self.b = b
        self.width = width

edges = [Edge(*[int(i) for i in input().split()]) for _ in range(edge_num)]
edges.sort(key=lambda e: e.width)  # 按 width 排序

for e in edges:
    print(f"({e.a}, {e.b}): {e.width}")

方法三：Comparator（比较器）

使用 functools.cmp_to_key 将比较函数转换为 key：

from functools import cmp_to_key

class Edge:
    def __init__(self, a: int, b: int, width: int):
        self.a = a
        self.b = b
        self.width = width

edges = [Edge(*[int(i) for i in input().split()]) for _ in range(edge_num)]
edges.sort(key=cmp_to_key(lambda x, y: x.width - y.width))

比较器必须满足：

• x < y 时返回 -1
• x > y 时返回 1
• x == y 时返回 0

---

二、多条件排序

按多个关键字升序排序

利用元组的字典序特性：

# 按 width 升序，width 相同时按 a 升序
edges.sort(key=lambda edge: (edge.width, edge.a))

或者使用比较器：

def compare(x, y):
    if x.width != y.width:
        return x.width - y.width
    return x.a - y.a

edges.sort(key=cmp_to_key(compare))

降序排序

edges.sort(key=lambda e: e.width, reverse=True)

---

三、坐标压缩

什么是坐标压缩？

将大范围的值映射到连续的自然数索引。

示例：

• 原始列表：{7, 3, 4, 1}
• 排序后：{1, 3, 4, 7}
• 压缩结果：{3, 1, 2, 0}

适用场景

当值域很大但需要用值作为数组索引时：

• 值域：0 ~ 10^9（无法直接作为数组索引）
• 实际不同值数量：N ≤ 10^6
• 压缩后：0 ~ N-1（可直接作为数组索引）

代码实现

# 方法1：简单压缩
values = [7, 3, 4, 1, 3]
sorted_unique = sorted(set(values))  # [1, 3, 4, 7]
compress = {v: i for i, v in enumerate(sorted_unique)}

compressed = [compress[v] for v in values]  # [3, 1, 2, 0, 1]

# 方法2：需要反向映射时
indices = sorted(set(values))
compress = {v: i for i, v in enumerate(indices)}
decompress = {i: v for i, v in enumerate(indices)}

---

四、例题：Rectangular Pasture

题目来源: USACO Silver - Rectangular Pasture

核心思想：使用坐标压缩将坐标映射到 0 ~ N-1 范围，以便使用二维前缀和数组。

代码实现

import sys

input = sys.stdin.readline

n = int(input().strip())
points = [list(map(int, input().strip().split())) for _ in range(n)]

# 坐标压缩：先按 y 排序
points.sort(key=lambda i: i[1])
for i in range(n):
    points[i][1] = i + 1

# 再按 x 排序
points.sort(key=lambda i: i[0])
for i in range(n):
    points[i][0] = i + 1

# 二维前缀和
psa = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
for x, y in points:
    psa[x][y] = 1

for x in range(1, n + 1):
    for y in range(1, n + 1):
        psa[x][y] += psa[x - 1][y] + psa[x][y - 1] - psa[x - 1][y - 1]

# 统计矩形数量
ans = n + 1

for s in range(n):
    for e in range(s + 1, n):
        srt, end = points[s][0], points[e][0]
        top = max(points[s][1], points[e][1])
        bottom = min(points[s][1], points[e][1])

        above = psa[end][n] - psa[srt - 1][n] - psa[end][top] + psa[srt - 1][top]
        below = psa[end][bottom - 1] - psa[srt - 1][bottom - 1]
        ans += (above + 1) * (below + 1)

print(ans)

关键点

• 坐标压缩后，原有坐标值不再需要，只用压缩后的索引
• 压缩后坐标范围：0 ~ N-1，可直接作为数组下标

---

五、例题：Static Range Queries

题目来源: Codeforces - Hard

题目描述：

• 有 N 个区间更新操作：每次在区间 [l, r) 上加 v
• 有 Q 个查询操作：查询区间 [l, r) 的元素之和
• 坐标范围：0 ~ 10^9，需要高效处理

核心思想：

1. 特殊索引：输入中出现的所有坐标（每个更新的左右端点、每个查询的左右端点）
2. 特殊区间：两个相邻特殊索引之间的区间，区间内所有元素值相同
3. 差分数组：用 +v 标记左端点，-v 标记右端点，求前缀和得到实际值
4. 双向映射：既要能用原始值找压缩索引（index[v]），也要能用压缩索引找原始值（coordinates[i]）

详细解释

1. 特殊索引与特殊区间

在整个范围 1 ~ 10^9 中，并非每个索引都会在更新中使用。输入中提到的每个索引称为特殊索引。两个连续的特殊索引之间的区间内，每个位置的值都相同——因为不可能有更新操作插入到两个特殊索引之间（否则会产生新的特殊索引）。

例如：更新 [3, 10) += 5，查询 [5, 8)，则特殊索引为 {3, 5, 8, 10}，特殊区间为 [3,5)、[5,8)、[8,10)。

2. 差分数组

对区间 [l, r) 加 v 时：

• 在位置 l 标记 +v（表示从 l 开始增加 v）
• 在位置 r 标记 -v（表示从 r 开始减少 v）

对这个差分数组求前缀和，就得到每个位置的值。

3. 前缀和与区间求和

对于查询 [l, r) 的和：

• 区间和 = 区间内每个元素的值 × 区间长度
• 如果我们知道每个特殊区间的值和长度，就可以求和

这引出了双重前缀和：

• 第一层前缀和：从差分数组得到每个特殊区间的值
• 第二层前缀和：从特殊区间的”值 × 长度”得到区间累计和

4. 双向坐标映射

与上一题（Rectangular Pasture）不同，本题需要同时知道：

• 原始值 → 压缩索引：index[value] 用于定位
• 压缩索引 → 原始值：coordinates[i] 用于计算区间长度

因为我们需要知道相邻特殊索引之间的距离（即特殊区间的长度）。

代码实现

# https://codeforces.com/gym/102951/problem/D

n, q = map(int, input().split())
diff_dict = dict()
coord_set = {-1}
queries = []

for _ in range(n):
    left, right, add_val = map(int, input().split())
    coord_set.add(left)
    coord_set.add(right)
    diff_dict[left] = diff_dict.get(left, 0) + add_val
    diff_dict[right] = diff_dict.get(right, 0) - add_val

for _ in range(q):
    left, right = map(int, input().split())
    coord_set.add(left)
    coord_set.add(right)
    queries.append((left, right))

coord_set = sorted(coord_set)
idx_dict = {coord_set[i]: i for i in range(len(coord_set))}

cur_value = 0
prefix_sum = [0]

for i in range(1, len(coord_set)):
    segment_len = coord_set[i] - coord_set[i - 1]
    segment_sum = cur_value * segment_len
    prefix_sum.append(prefix_sum[-1] + segment_sum)
    cur_value += diff_dict.get(coord_set[i], 0)


for (l, r) in queries:
        left_idx = idx_dict[l]
        right_idx = idx_dict[r]
        ans = prefix_sum[right_idx] - prefix_sum[left_idx]
        print(ans)

关键点

• 双向映射：index[v] 获取压缩索引，coordinates[i] 获取原始值
• 差分数组技巧：用 +v、-v 标记区间起止，前缀和得到实际值
• 空间优化：只需存储出现的坐标，最多 2·(N+Q) 个
• 时间复杂度：预处理 O((N+Q) log(N+Q))，查询 O(1)

---

六、总结

技术	用途
Key 函数	按单/多关键字排序，最常用
比较器	复杂排序逻辑
坐标压缩	大范围值映射到小范围索引

核心思想：将问题转化为可以用数组下标处理的形式。