离散化

一句话算法

离散化保留大小关系，把很大的值域压缩成连续的小编号。

问题模型

有一组数值 $a_1,a_2,\dots,a_n$，它们的值域可能很大，例如坐标达到 $10^9$，但真正出现过的数只有 $n$ 个。

很多算法需要用数组下标表示这些值，例如树状数组、线段树、桶统计。如果直接按原值开数组，会浪费空间甚至无法开出数组。

离散化要做的是：

• 相同的原值映射到相同编号。
• 原值大小关系不变：若 $x<y$，则 $id(x)<id(y)$。
• 编号连续，通常为 $1,2,\dots,m$。

核心直觉

我们不关心数值本身有多大，只关心这些数之间的相对顺序。

例如：

1000000000  -5  1000000000  7

出现过的不同值排序后是：

-5  7  1000000000

于是映射为：

-5 -> 1
7 -> 2
1000000000 -> 3

原来的巨大值域被压缩成了 $[1,3]$，但大小关系没有丢。

算法步骤

1. 把所有需要离散化的值收集到数组 xs。
2. 对 xs 排序。
3. 使用 unique 去掉重复值。
4. 对每个原值 x，用 lower_bound 找到它在 xs 中的位置。
5. 位置加一，得到 $1$ 下标离散编号。

离散化前要先收集所有可能被查询或修改到的值。

如果后续出现了没有加入 `xs` 的值，`lower_bound` 只能告诉你它应该插入哪里，不能保证这是合法映射。

算法证明

关键不变量：xs 排序去重后，按升序保存所有出现过的不同值。

1. 唯一性 去重后每个原值在 xs 中只出现一次，所以相同原值一定映射到同一个位置。

2. 保序性 xs 是升序数组。若 $x<y$，则 $x$ 在 xs 中的位置一定在 $y$ 前面。

3. 连续性 xs 的下标天然连续。若不同值个数为 $m$，则编号正好是 $1$ 到 $m$。

所以离散化后的编号既保留大小关系，又把值域压缩成连续小范围。

复杂度分析

• 收集元素：$O(n)$。
• 排序去重：$O(n\log n)$。
• 单次查询映射：$O(\log n)$。
• 空间复杂度：$O(n)$。

如果要查询很多次，可以把每个原值到编号的映射存入哈希表，把查询降到均摊 $O(1)$。但竞赛中 vector + lower_bound 更简单稳定。

代码实现

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

        #include <bits/stdc++.h>
using namespace std;

struct Discrete {
    vector<int> xs;

    void clear() {
        xs.clear();
    }

    void add(int x) {
        xs.push_back(x);
    }

    void build() {
        sort(xs.begin(), xs.end());
        xs.erase(unique(xs.begin(), xs.end()), xs.end());
    }

    // 返回 x 离散化后的 1 下标编号。
    int get(int x) const {
        return lower_bound(xs.begin(), xs.end(), x) - xs.begin() + 1;
    }

    // 找不到时返回 -1，适合查询不确定是否出现过的值。
    int get_maybe(int x) const {
        auto it = lower_bound(xs.begin(), xs.end(), x);
        if (it == xs.end() || *it != x) return -1;
        return it - xs.begin() + 1;
    }

    // 根据 1 下标编号找回原值。
    int origin(int k) const {
        return xs[k - 1];
    }

    int size() const {
        return (int)xs.size();
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> a(n);
    Discrete disc;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        disc.add(a[i]);
    }

    disc.build();

    cout << disc.size() << '\n';
    for (int i = 0; i < n; i++) {
        if (i > 0) cout << ' ';
        cout << disc.get(a[i]);
    }
    cout << '\n';

    return 0;
}
    

测试用例

输入：

6
100 5 100 -3 5 9

输出：

4
4 2 4 1 2 3

不同值排序后为：

-3 5 9 100

所以原序列映射为：

100 -> 4
5 -> 2
100 -> 4
-3 -> 1
5 -> 2
9 -> 3

应用分类详解

离散化的本质是“值域压缩”。当值很大但不同值数量不多，并且算法只依赖大小关系或相等关系时，就应该考虑离散化。

一、坐标压缩

典型模式： 坐标范围巨大，但只会操作有限个坐标点。

识别信号： 题面出现“坐标可达 $10^9$”“只给出 $n$ 个点”“需要按坐标开数组”。

核心建模： 收集所有出现过的坐标，排序去重后把坐标映射成连续编号。

二、配合树状数组或线段树

典型模式： 原值很大，但需要按值域维护前缀信息、排名、数量。

识别信号： 题面要求“统计比当前数小的数量”“排名”“逆序对”，且数值范围远大于 $n$。

核心建模： 把值离散成 $1..m$，再用树状数组或线段树维护这些编号上的信息。

三、状态压缩前的重编号

典型模式： 原编号不连续，但后续算法要求编号连续。

识别信号： 输入给出字符串、巨大编号、稀疏编号，但需要建图或数组 DP。

核心建模： 把出现过的对象映射到连续整数编号，再用普通数组建结构。

四、离线处理端点

典型模式： 操作全部提前给出，端点很大，但查询只发生在这些端点附近。

识别信号： 题面允许先读入全部操作；操作端点值域大，操作数量不大。

核心建模： 先收集所有操作涉及的端点，有时还要加入 x+1 或相邻边界，保证区间长度信息不丢。

经典例题

1. luogu-P1908

逆序对中的数值范围可能较大，但只需要比较大小。先离散化，再用树状数组统计每个数前面已经出现过多少个更大的数。

2. luogu-P5490

扫描线求矩形面积并。矩形坐标可能很大，但线段树只需要维护出现过的 y 坐标相邻区间，因此要先对 y 坐标离散化。

3. luogu-P3368

如果区间端点本身来自巨大坐标，可以先离散化端点，再把区间修改转到压缩后的编号上处理。

参考

• 旧版文章：Rbook_ejs_old/book/base/discrete/index.md
• 旧版模板：Rbook_ejs_old/book/base/discrete/discrete.cpp