第 36 章压缩空间——离散化

🏗️ 前情回顾：上一章你学会了前缀和与差分，区间求和 O(1)、区间修改 O(1)，好用极了。但有一个尴尬的问题：如果坐标范围是 -10⁹ 到 10⁹，但实际只有 10⁵ 个点有数据，你还能开 2×10⁹ 大小的数组吗？显然不能——内存直接爆炸。这一章就要解决这个矛盾：让稀疏的大坐标"压缩"到紧凑的小下标。

🎯 本章目标

学完这一章，你能：

理解离散化的意义：保留相对顺序，压缩坐标范围
掌握离散化三步走：排序 → 去重 → 二分查找下标
熟练使用 lower_bound 实现 O(log n) 的坐标映射
将离散化与前缀和、差分结合，解决大范围坐标问题
解决火烧赤壁、覆盖问题等经典离散化应用题

📖 故事引入

假设你是城市规划师，要在地图上标记 100 栋楼的位置，然后统计被覆盖的路段。地图从西经 0 米到东经 10⁹ 米——但只有 100 个地方有楼。

如果你给每个"米"建一个数组元素，需要 10⁹ 个格子——上百 MB 内存，而且其中 99.99999% 都是空的！

但仔细想想：你关心的只是楼与楼之间的相对位置。楼 A 在东经 5000 米，楼 B 在东经 3×10⁸ 米——你只需要知道"B 在 A 的右边"，不需要知道它们之间具体隔着多少空地。

这就是离散化的精髓：把"100 栋楼"映射成"1 到 100 的编号"。原来的坐标可能是 {5000, 300000000, 700000000}，离散化后变成 {1, 2, 3}。相对顺序没变，但坐标范围从 10⁹ 压缩到了 100。

🧱 知识讲解

36.1 为什么需要离散化

总结三个痛点：

场景	问题	离散化后
坐标范围 -10⁹~10⁹，但只有 10⁵ 个点	数组开不下	下标范围 1~10⁵
用前缀和统计区间覆盖	2×10⁹ 的差分数组放不下	1~2×10⁵ 轻松
排序后需要保留"原始坐标"	坐标太大不能当数组下标	用"排名"当下标

📦 类比：离散化就像考试排名。你在年级里考了 685 分——这个具体分数不重要。重要的是"你是第 3 名"。排名保留了相对顺序（第 1 > 第 2 > 第 3），但把"0~750"的分数范围压缩到了"1~N"。

36.2 离散化三步走

假设有一组原始坐标（可能有重复）：

原始数据：{100000, 5, 3, 5, 200000000}

Step 1：排序 → {3, 5, 5, 100000, 200000000}

Step 2：去重 → {3, 5, 100000, 200000000}（只保留不重复的值，存到数组 b 中）

Step 3：二分查找 → 对每个原始值，用 lower_bound 找到它在去重数组 b 中的下标，这个下标就是离散化后的值。比如 100000 → b 中下标为 2（0-based）或 3（1-based）。

cpp

#include <iostream>
#include <algorithm>
using namespace std;

int a[100005];          // 原始数据
int b[100005];          // 去重后的有序副本
int n, m;               // n 个原始值，m 个不重复值

void discrete() {
    // Step 1: 复制并排序
    for (int i = 1; i <= n; i++) b[i] = a[i];
    sort(b + 1, b + n + 1);

    // Step 2: 去重（unique 把重复的移到末尾，返回新末尾迭代器）
    m = unique(b + 1, b + n + 1) - (b + 1);  // m = 不重复的元素个数
}

// Step 3: 查询原始值 x 离散化后的下标（1-based）
int getID(int x) {
    return lower_bound(b + 1, b + m + 1, x) - b;
}

unique 做了什么？它把相邻重复的元素"挤"到末尾，返回指向"第一个重复垃圾"的迭代器。用 unique(b+1, b+n+1) - (b+1) 就得到了不重复元素的个数。

⚠️ unique 只移除相邻重复，所以必须先 sort！unique 不会真正删除元素，只是把不重复的挪到前面。

36.3 `lower_bound` 详解

lower_bound(begin, end, x) 返回第一个 ≥ x 的位置的迭代器。

cpp

int b[] = {0, 3, 5, 100, 200};  // b[0] 不用
// lower_bound(b+1, b+5, 5) → 指向 b[2]（值=5）
// lower_bound(b+1, b+5, 7) → 指向 b[3]（值=100，第一个≥7）
// lower_bound(b+1, b+5, 300) → 指向 b[5]（end，没找到）

对于离散化，由于 x 一定在去重数组 b 中（它就是从原始数据里来的），lower_bound 一定精准命中，返回的就是 x 离散化后的 1-based 下标。

36.4 离散化 + 前缀和/差分组合

这是离散化最经典的应用场景——区间覆盖问题。

火烧赤壁：

数轴上有 n 条线段 [lᵢ, rᵢ]，求这些线段覆盖的总长度（重复覆盖只算一次）。

如果坐标范围很大（如 10⁹），但 n 很小（如 10⁵），直接开差分数组会爆内存。怎么办？离散化！

思路：

收集所有线段端点（共 2n 个坐标），离散化
用差分数组（大小为 2n）在离散化后的坐标上进行区间加法
还原差分，统计被覆盖的区间段
关键：累计长度时要映射回原始坐标——离散化后相邻两个位置 i 和 i+1 之间代表原始坐标的区间 [b[i], b[i+1])，长度是 b[i+1] - b[i]

cpp

struct Segment { int l, r; } seg[100005];
int pos[200005];   // 所有端点，用于离散化（大小 2n）
int diff[200005];  // 差分数组
int m;             // 去重后的坐标数

int main() {
    int n; cin >> n;
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        cin >> seg[i].l >> seg[i].r;
        pos[++cnt] = seg[i].l;
        pos[++cnt] = seg[i].r;
    }
    
    // 离散化
    sort(pos + 1, pos + cnt + 1);
    m = unique(pos + 1, pos + cnt + 1) - (pos + 1);
    
    // 差分：在离散化后的下标上操作
    for (int i = 0; i < n; i++) {
        int L = lower_bound(pos + 1, pos + m + 1, seg[i].l) - pos;
        int R = lower_bound(pos + 1, pos + m + 1, seg[i].r) - pos;
        diff[L]++;     // 从 L 开始覆盖
        diff[R]--;     // 到 R 结束覆盖（注意 R 对应的是 r 的位置，覆盖区间是 [L, R) ）
    }
    
    // 还原差分，统计长度
    int ans = 0, cur = 0;
    for (int i = 1; i < m; i++) {
        cur += diff[i];
        if (cur > 0) {  // 当前段 [pos[i], pos[i+1]) 被覆盖
            ans += pos[i+1] - pos[i];
        }
    }
    cout << ans << endl;
    return 0;
}

💡 关键细节：统计长度时，离散化后的下标 i 对应原始坐标 pos[i]，下标 i 和 i+1 之间的"空隙"代表一段连续区间 [pos[i], pos[i+1])。被覆盖时，累加的是 pos[i+1] - pos[i]，而不是 1。

**一类常见的"覆盖问题"**也可以类似处理：

求被覆盖最多次的点的覆盖次数 → 差分还原时取 cur 的最大值
求刚好被 k 条线段覆盖的总长度 → 差分还原时 if (cur == k) ans += pos[i+1] - pos[i]

36.5 离散化的"双向映射"

有时候你需要在离散化后的下标和原始坐标之间来回转换：

方向	方法
原始坐标 → 离散下标	`lower_bound(b+1, b+m+1, x) - b`
离散下标 → 原始坐标	`b[idx]`（查去重数组）

保留去重数组 b 就可以随时做反向映射，不要丢弃它！

✋ 动手试试

试试 1：输入 n 个可能有重复的整数，输出它们离散化后的值（每个原始值对应一个 1-based 下标）。

试试 2：用离散化 + 差分解决"火烧赤壁"问题。输入 3 条线段：[1, 5], [3, 8], [10, 12]，输出被覆盖总长度（重叠部分只算一次）。结果应为 10。

试试 3：写一个带离散化的"区间覆盖计数"——输入 n 条线段，输出被覆盖最多次的那个点的被覆盖次数。

⚠️ 容易犯的错

错 1：离散化后直接用下标差当长度

❌ for (int i = 1; i < m; i++) ans += (cur > 0 ? 1 : 0); ——每条离散段都计为 1，忽略了原始坐标的真实间隔。

✅ ans += (cur > 0 ? pos[i+1] - pos[i] : 0);

错 2：`unique` 之前忘了 `sort`

❌ 数组 {5, 3, 5, 100} 直接 unique，结果是 {5, 3, 100, ?} ——3 和第二个 5 没被清理。

✅ 必须先 sort 再 unique。

错 3：差分区间处理时 R 的端点多写了 +1

❌ 在线段覆盖问题中写 diff[R+1]-- ——离散化后的 R 已经是该点的下标，R+1 可能对应一个很大的原始坐标间隙，导致统计偏大。

✅ 线段覆盖用 diff[L]++; diff[R]--;（区间是 [L, R) 半开区间），然后统计 [pos[i], pos[i+1]) 的长度。

错 4：`lower_bound` 返回值没有减去数组起始地址

❌ int id = lower_bound(b+1, b+m+1, x); ——返回的是迭代器（地址），不是下标。

✅ int id = lower_bound(b+1, b+m+1, x) - b; ——减去数组首地址得到下标。

📝 练习

基础题

1. 选择题

（1）离散化的主要目的是：
A. 加速排序 B. 压缩坐标范围 C. 去重 D. 加密数据

（2）lower_bound(b+1, b+m+1, x) 返回的是：
A. 第一个 > x 的位置 B. 第一个 ≥ x 的位置 C. 最后一个 < x 的位置 D. x 本身的地址

（3）unique 的前提是数组已经：
A. 倒序 B. 随机序 C. 升序 D. 无要求

2. 填空题

（1）离散化三步走：____ → ____ → ____。

（2）去重后元素个数 = unique(b+1, b+n+1) - ___。

（3）离散化后下标 i 对应的原始坐标值是 ____。

提高题

3. 编程题 — 离散化模板

输入 n 个整数，按输入顺序输出每个数离散化后的值（1-based）。例如输入 {100, 5, 3, 5}，输出 3, 2, 1, 2。

4. 编程题 — 简单区间覆盖

输入 n 条线段 [l, r]（坐标范围 ≤ 10⁹，n ≤ 10⁵），输出正好被 2 条线段覆盖的总长度。

挑战题

5. 编程题 — 火烧赤壁（完整版）

输入 n 条线段，求所有线段覆盖的总长度（重叠只算一次）。坐标范围 ≤ 10⁹。

6. 编程题 — 电影放映

电影院有 n 场电影，每场开始时间 lᵢ、结束时间 rᵢ、愉悦值 wᵢ。你同一时间只能看一场电影。求最大总愉悦值。（提示：离散化时间 + DP。离散化后时间点 ≤ 2n。）

🧠 本章小结

离散化 = 保留顺序，压缩范围

三步走：
  ① 排序   sort(b+1, b+n+1)
  ② 去重   m = unique(b+1, b+n+1) - (b+1)
  ③ 映射   id = lower_bound(b+1, b+m+1, x) - b

核心作用：
  坐标范围 10⁹ → 离散下标 1~N
  让前缀和/差分在大范围坐标上也能用

关键注意：
  ✓ unique 前必须 sort
  ✓ lower_bound 返回值要减去 b
  ✓ 统计真实长度用 pos[i+1] - pos[i]，不用 1
  ✓ 保留去重数组 b 用于反向映射

📝 配套练习

共5题。离散化三步走(排序→去重→二分)每题都用一遍，和前缀和/差分/并查集配合。。★核心（课堂必做） ◆拓展（课后练习）

级别	题号	链接	覆盖知识点
★ 核心	luogu-P1496	https://hydro.ac/p/luogu-P1496	离散化+差分、段统计
◆ 拓展	luogu-P1884	https://hydro.ac/p/luogu-P1884	离散化+二维差分、矩形覆盖
◆ 拓展	luogu-P1955	https://hydro.ac/p/luogu-P1955	离散化+并查集
◆ 拓展	luogu-P1904	https://hydro.ac/p/luogu-P1904	离散化、天际线
◆ 拓展	luogu-P5937	https://hydro.ac/p/luogu-P5937	离散化+差分、覆盖长度

💡 练习建议：先完成 1 道★核心题，确保掌握本章基本方法；再完成 4 道◆拓展题，覆盖不同变式和细节。

配套练习

共5题。离散化三步走(排序→去重→二分)每题都用一遍，和前缀和/差分/并查集配合。★核心（课堂必做） · ◆拓展（课后练习）

级别	题号	链接	覆盖知识点
★ 核心	luogu-P1496	https://hydro.ac/p/luogu-P1496	离散化+差分、段统计
◆ 拓展	luogu-P1884	https://hydro.ac/p/luogu-P1884	离散化+二维差分、矩形覆盖
◆ 拓展	luogu-P1955	https://hydro.ac/p/luogu-P1955	离散化+并查集
◆ 拓展	luogu-P1904	https://hydro.ac/p/luogu-P1904	离散化、天际线
◆ 拓展	luogu-P5937	https://hydro.ac/p/luogu-P5937	离散化+差分、覆盖长度

练习建议：先在课堂完成 1 道★核心题，掌握本章基本方法；课后完成 4 道◆拓展题，覆盖不同变式和细节。

自查清单：

[ ] 我理解离散化解决"坐标太大、数据稀疏"的问题
[ ] 我能独立写出离散化三步走（排序→去重→二分映射）
[ ] 我会用 lower_bound 查询离散化下标
[ ] 我能将离散化与差分结合解决区间覆盖问题
[ ] 我知道统计长度时要映射回原始坐标
[ ] 我能区分什么时候需要离散化、什么时候直接用原始坐标

🚀 下章预告：现在你的算法工具箱已经塞满了——枚举、模拟、双指针、前缀和、离散化……但还有一个基础难题没解决：当数字大到 long long 也装不下的时候怎么办？下一章《大数计算——高精度运算》，教你用字符串模拟大数运算，突破数据类型的上限！🔢

第 36 章 压缩空间——离散化 ​

🎯 本章目标 ​

📖 故事引入 ​

🧱 知识讲解 ​

36.1 为什么需要离散化 ​

36.2 离散化三步走 ​

36.3 lower_bound 详解 ​

36.4 离散化 + 前缀和/差分组合 ​

36.5 离散化的"双向映射" ​

✋ 动手试试 ​

⚠️ 容易犯的错 ​

错 1：离散化后直接用下标差当长度 ​

错 2：unique 之前忘了 sort ​

错 3：差分区间处理时 R 的端点多写了 +1 ​

错 4：lower_bound 返回值没有减去数组起始地址 ​

📝 练习 ​

基础题 ​

提高题 ​

挑战题 ​

🧠 本章小结 ​

📝 配套练习 ​

配套练习 ​