Skip to content

离散化

把大值域压缩成小下标,让数组和数据结构放得下。

Updated View as Markdown

有些题目的数值范围大得离谱,坐标可以到 10^9,但实际出现的不同的数只有 10^5 个。想用数组下标直接表示这些值,内存立刻爆掉。离散化就是为这种情况准备的。

本章的知识点与 GESP、CSP-J/S 大纲的对应关系如下。

考试 大纲要求 本章位置
NOI 提高级 2.4.2 算法策略:离散化【6】 全章
CSP-J/S 第一轮 离散化的思想与实现是提高级初赛的常见考点 全章
CSP-J/S 提高级 2.4.2 算法策略:离散化配合树状数组(逆序对、二维偏序) 综合示例、练习 5
GESP C++ 八级 多关键字比较与排名计算(离散化的直接应用) 练习 1、练习 6

什么时候用

判断标准只有一条:只需要知道各个数之间的大小关系,不需要知道实际差值。

  • 一道题给出 n 个人的身高,范围到 10^9,要按身高分等级。具体是多少厘米不重要,排名重要。
  • 要在数轴上做区间覆盖,坐标到 10^9,但只有 2 \times 10^5 个端点。可以把这些端点压缩成 1 到 2 \times 10^5 的下标,用树状数组或线段树处理。

反例也要记住:如果题目要算「两个坐标之间隔了多长」或者「面积是多少」,差值本身有意义,离散化时就得额外记录原坐标,否则会把距离压缩掉。

三步做法

  1. 排序。把所有需要离散化的数收集到一个数组里排好序。
  2. 去重。相同的值只保留一个,否则同一个值会映射到不同的下标。
  3. 二分。对每个原数,用二分查出它在去重数组里的位置,这个位置就是新的下标。
#include <bits/stdc++.h>
using namespace std;

int a[100005]; // 原始数组,1-based
int b[100005]; // 用于离散化的数组

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        b[i] = a[i];
    }

    // 1. 排序
    sort(b + 1, b + n + 1);
    // 2. 去重,tot 是不同值的个数
    int tot = unique(b + 1, b + n + 1) - (b + 1);
    // 3. 二分映射,把 a[i] 换成它在 b 中的排名(从 1 开始)
    for (int i = 1; i <= n; i++) {
        a[i] = lower_bound(b + 1, b + tot + 1, a[i]) - b;
    }

    for (int i = 1; i <= n; i++) cout << a[i] << " ";
    return 0;
}

lower_bound 返回的是第一个大于等于目标的位置,减掉数组起点后得到下标,恰好是 1 到 tot 之间的排名。

一个例子

输入 100 3 1000000000 3 100。

  • 收集并排序:3 3 100 100 1000000000
  • 去重后:3 100 1000000000,共 3 个不同的值
  • 映射关系:3 → 1,100 → 2,1000000000 → 3

原来的数组变成 2 1 3 1 2。数值范围从 10^9 压到 3,但大小关系完全没变:原来 3 最小、100 居中、1000000000 最大,现在依然是这个顺序。

复杂度

步骤 复杂度
排序 O(n \log n)
去重 O(n)
每次二分查找 O(\log n)
总计 O(n \log n)

离散化的典型应用

离散化很少单独出现,它通常是别的方法的「前置步骤」。常见的组合有:

组合 解决的问题 关键点
离散化 + 差分 坐标到 10^9 的区间覆盖、区间加 把端点离散化后再开数组
离散化 + 计数 统计每个值出现的次数 压缩后的排名直接当数组下标
离散化 + 树状数组 / 线段树 逆序对、区间第 k 小 这些结构要求下标连续且不大
离散化 + 哈希 值到编号的映射 用哈希表代替二分
坐标压缩 扫描线、二维矩阵问题 要额外保留每个下标的原坐标
离散化 + 后缀和 竞赛排名、并列留空名次 名次 = 严格比它大的元素数 + 1
离散化 + 二维偏序 统计「前面且更小」的数对、LIS 优化 本质是逆序对的推广

其中最有名的是用离散化求逆序对:值域可能到 10^9,没法直接开桶统计;但把每个数换成「它在所有数里排第几」之后,可能的下标就只剩 n 种,树状数组就放得下了。树状数组负责统计「当前位置之前已经出现了多少个比它小的数」。

综合示例:离散化 + 树状数组求逆序对

题目描述

给定一个长度为 n 的整数序列,求其中逆序对的个数。逆序对指满足 i < j 且 a_i > a_j 的数对 (i, j)。

输入格式

第一行一个整数 n;第二行 n 个整数。

输出格式

输出一个整数,表示逆序对的个数。

数据范围

  • 1 \le n \le 10^5,|a_i| \le 10^9。

输入输出样例

输入

4
3 2 1 4

输出

3

(逆序对是 (3,2)、(3,1)、(2,1)。)

题目分析

这是离散化最经典的应用场景,没有之一。为什么要离散化,看数据范围就明白了:|a_i| 可以到 10^9,而 n 只有 10^5。如果用桶计数(cnt[a[i]]++),数组得开到 10^9,直接爆内存;但不同的数最多只有 n = 10^5 个,离散化之后下标范围就变成 1 \sim n,一切都放得下了。

思路:

  1. 离散化:把所有数排序去重,每个数映射到它的排名(1 \sim n);
  2. 用树状数组维护每个排名出现过的次数:从左往右扫原序列,扫到 a_i 时:
    • 先查「已经出现过多少个比它大的数」——这些数都在 a_i 前面,且大于它,正好构成逆序对,累加进答案;
    • 再把 a_i 的排名计入树状数组。

查询「比它大的有多少个」的方式:已经扫过 i-1 个数,其中不大于 a_i 的有 query(rank) 个(树状数组的前缀和),所以比它大的就是 (i-1) - query(rank)。代码里写成 query(tot) - query(rank),其中 query(tot) 就是「已扫过的总数」,两者等价。

为什么这里必须要树状数组? 因为如果每扫一个数都把前面的数重新数一遍,就是 O(n^2);而树状数组的查询和修改都是 O(\log n),总复杂度 O(n \log n),配上离散化的 O(n \log n),整体仍是 O(n \log n)。

逆序对还有另一个同样经典的解法:归并排序(在「排序算法」章节里讲过),O(n \log n) 且不需要离散化。两种做法都要会,比赛时归并排序更省事,而「离散化 + 树状数组」这个组合更能体现离散化的价值,也是后面学习二维偏序、动态逆序对的基础。

参考代码

几个要注意的点:

  • 答案要用 long long。逆序对最多约 n(n-1)/2 \approx 5 \times 10^9,超过 int。
  • 用 query(tot) - query(rk) 而不是 (i-1) - query(rk) 也行,但前者不依赖循环变量,含义更清楚:「已出现的总数减去不大于它的」。
  • 重复值的处理:这里用「严格大于」统计,所以相同值不算逆序对,query(rk) 把「等于」的那些也包含进了「不大于」,正好符合要求。如果题目要求「大于等于」算逆序对,就要改成 query(rk - 1)。

常见易错点

  • 忘记去重。 同一个值被映射成不同的下标,后面的统计就会重复。
  • 把压缩后的排名当成原值。 离散化之后的 1、2、3 只是「第几小」,不是真实数字。需要用原值时,要在映射表里回查。
  • 压缩后直接算差值。 坐标类题目里,离散化后相邻两个下标的间隔通常不是 1。要算距离或长度,必须额外记下每个下标对应的原坐标。
  • 查询的值不在集合里。 对没出现过的值做 lower_bound,得到的是它该插入的位置,当成下标用就错了。
  • lower_bound 的区间写错。 下标从 1 开始时区间是 b + 1 到 b + tot + 1,开闭区间差一位结果就全错。
  • 直接覆盖原数组。 需要按原顺序输出时,先备份一份原始数据。
  • 把离散化当成加密。 它不改变数值含义,只是换了个表示方式。
  • 并列排名直接用「不同值个数 − 排名 + 1」。 那是「比它大的不同值个数 + 1」,只有当每个值恰好出现一次时才等于正确答案;有并列时必须用「比它大的元素个数 + 1」。
  • 逆序对里相同值算错。 用 query(rk) 配「总数减它」是严格大于(相同值不算);要统计「大于等于」时得改成 query(rk - 1)。
  • 逆序对答案用了 int。 最多约 5 \times 10^9,必须 long long。

练习

下面的练习都已经收录进题库,点击每道题的「在线评测练习」可以直接提交评测;题面与数据范围以题库为准,课堂上的分析和代码则只围绕本章的「离散化」展开,方便对照前面的三步做法直接套用。

练习 1:输出排名

在线评测练习:P1513 输出排名

题目描述

给定 n 个整数,输出每个数在全部数中的排名。相同的数排名相同,最小的数排名为 1。

输入格式

第一行一个整数 n。

第二行包含 n 个整数,相邻两个整数之间用一个空格隔开。

输出格式

输出一行 n 个整数,依次为每个数的排名,相邻两个整数之间用一个空格隔开。

数据范围

  • 1 \le n \le 10^5。
  • |a_i| \le 10^9。

输入输出样例

输入

5
100 3 1000000000 3 100

输出

2 1 3 1 2

输入

3
5 5 5

输出

1 1 1

题目分析

本章「三步做法」的直译版:排序、去重、二分。这里的排名本身就是离散化后要用的新下标,所以这道题等于把离散化的中间结果直接打印出来。

为什么排名可以直接当新下标? 因为 lower_bound 在去重后的数组里找位置,返回值恰好是「严格小于它的不同值个数」,加 1 就是从 1 开始的排名。unique 保证了相同的数落在同一个位置上——第二个样例 5 5 5 输出 1 1 1,就是这一步在起作用。如果漏掉去重,同样的 5 会映射到三个不同下标,排名立刻全乱,这正是「常见易错点」的第一条。

两个实现细节呼应本章的易错点清单:

  • 必须备份原数组。a 读进来后要输出每个数的排名,而 b 是排序去重用的副本。如果我们直接在 a 上排序去重,输入顺序就丢了,没法按原顺序输出。本章易错点里「直接覆盖原数组」说的就是这个。
  • lower_bound 的区间是 b 到 b + tot,不是 b + n。去重之后有效长度只有 tot,拿 n 当右端点会把 b 里 tot 之后那些残留的旧值也纳入二分范围,结果就错了。

复杂度就是本章的 O(n \log n):排序 O(n \log n),去重 O(n),每个元素二分一次共 O(n \log n)。

参考代码

练习 2:统计每个不同值的出现次数

在线评测练习:P1478 各分数的人数

题目描述

给定 n 个学生的成绩,请按分数从小到大的顺序,输出每个出现过的分数以及对应的人数。

输入格式

第一行包含一个正整数 n。

第二行包含 n 个整数,表示每名学生的成绩,相邻两个整数之间用一个空格隔开。

输出格式

按分数从小到大输出若干行,每行包含两个整数:分数和该分数的人数,中间用一个空格隔开。

数据范围

  • 1 \le n \le 10^5。
  • 0 \le 成绩 \le 100。

输入输出样例

输入

10
85 90 85 70 90 85 100 60 70 85

输出

60 1
70 2
85 4
90 2
100 1

题目分析

这是「离散化 + 计数」的标准形态:把压缩后的排名直接当计数数组的下标用。

本题的数据范围有个值得注意的地方:成绩只到 100,所以这题其实用桶就能做(开一个 101 大小的 cnt 数组,cnt[x]++),不需要离散化。但正因为值域小,它更适合用来把离散化的思路先走通一遍——把「桶的下标」换成「离散化后的排名」,代码结构几乎一样:

桶计数 离散化 + 计数
下标是什么 原始值 x 排名 r \in [1, tot]
数组多大 值域大小(101) 不同值个数 tot \le n
什么时候必须用 值域很小 值域到 10^9,桶开不下

关键一步是下面的对应关系:

  • b[i](去重后的数组)存的是原始值,用来输出第一列;
  • cnt[i] 存的是排名为 i 的值的出现次数,用来输出第二列。

两者下标相同,所以第 i 行输出 b[i] 和 cnt[i] 是天然配对的。这正是本章反复强调的「离散化不改变数值含义,只是换了个表示方式」——需要原值时,回到 b 里查即可。

如果哪天数据范围改成 |成绩| \le 10^9,这段代码一行都不用改(除了把 int 换成 long long 防溢出),这就是离散化的价值:它把「值域大小」从复杂度里彻底拿掉了。

参考代码

练习 3:区间最大覆盖次数

在线评测练习:P1512 区间最大覆盖次数

题目描述

数轴上有 n 个闭区间 [l_i, r_i],求被覆盖次数最多的位置被覆盖了多少次。

输入格式

第一行包含一个整数 n。

接下来 n 行,每行包含两个整数 l_i、r_i,中间用一个空格隔开,表示一个闭区间。

输出格式

输出一行一个整数,表示单个位置被覆盖的最大次数。

数据范围

  • 1 \le n \le 10^5。
  • 0 \le l_i \le r_i \le 10^9。

输入输出样例

输入

3
1 5
3 8
6 10

输出

2

输入

2
1 1
1 1

输出

2

位置 1 被两个区间各覆盖一次,共 2 次。

题目分析

本章「离散化 + 差分」组合的入门题。如果坐标范围小,直接在数轴上开差分数组就行;但坐标到 10^9,数组开不下——这正是本章开头说的那种「数值范围大得离谱,实际出现的值却很少」的场景。

关键观察:覆盖次数只会在区间端点处发生变化。 两个端点之间的一整段,覆盖次数完全相同,所以没必要逐点处理,只需要在 2n 个端点处记录事件。

于是做法是本章三步的直接应用:

  1. 把全部 2n 个端点(左右端点都收)排序去重;
  2. 每个区间 [l, r] 映射成压缩下标 [l_i', r_i'],在 d[l']++、d[r' + 1]-- 做差分;
  3. 顺着压缩后的下标扫一遍前缀和,最大值就是答案。

为什么这里不需要保留原坐标? 因为题目只问「最多次数」,问的是次数而不是长度。次数在每一段里是常数,压缩掉距离不影响它。这和练习 4 形成对照——那边要算整数点个数,距离本身是答案的一部分,就必须把差值算回来。这就是本章「什么时候用」里那条反例的边界。

d 数组必须开到 2n + 2:差分要写 d[ri + 1],当 ri 正好是最后一个压缩下标 tot 时,ri + 1 就落到了 tot + 1。少开一格就是越界写,这类错误往往在特定数据上才崩,很难查。

第二个样例 1 1 出现两次是用来检查边界的:闭区间 [1,1] 是一个点,l' == r',d[l']++ 和 d[l' + 1]-- 必须都落在正确位置,答案才是 2。

参考代码

练习 4(进阶):区间并集的整数点个数

在线评测练习:P1511 区间并集的整数点个数

题目描述

数轴上有 n 个闭区间 [l_i, r_i],求这些区间一共覆盖了多少个不同的整数点(被多个区间重复覆盖的点只算一次)。

输入格式

第一行包含一个整数 n。

接下来 n 行,每行包含两个整数 l_i、r_i,中间用一个空格隔开,表示一个闭区间。

输出格式

输出一行一个整数,表示被覆盖的不同整数点个数。

数据范围

  • 1 \le n \le 10^5。
  • |l_i| \le 10^9,l_i \le r_i。

输入输出样例

输入

3
1 5
3 8
10 12

输出

11

并集是 [1, 8] \cup [10, 12],1 到 8 共 8 个整数点,10 到 12 共 3 个,一共 11 个。

输入

2
-3 -1
0 0

输出

4

[-3,-1] 含 3 个整数点,[0,0] 含 1 个,没有重叠。

题目分析

这道题是练习 3 的反面教材,也是本章「反例」那条最典型的落地:这道题的答案就是距离,所以离散化之后必须把原坐标的差值算回来。

如果硬套练习 3 的做法(只数「有多少段被覆盖」),会得到「被覆盖的段数」而不是「整数点个数」。因为两个相邻离散点之间可能隔着成百上千个整数点,压缩之后这些点全被压成了一个下标。这对应易错点里那两条:「压缩后直接算差值」和「把压缩后的排名当成原值」。

正确做法:

  1. 把闭区间 [l, r] 改写成左闭右开 [l, r+1)。这一步很关键——它让「闭区间含全部整数点」变成「区间长度为点数」,避免了 +1/-1 的反复纠结;
  2. 把 l 和 r + 1 都收进离散化数组(注意此时收的是 R1 = r + 1,不是 r);
  3. 差分后从 i = 1 扫到 tot - 1,若 cover > 0 就把 b[i] - b[i-1] 累加进答案。

b[i] - b[i-1] 这一项就是「下标 i-1 到 i 之间那一段原始坐标的跨度」——这就是本章说的「额外保留每个下标对应的原坐标」的具体形态:b 数组本身就是那张映射表,压缩下标 i 对应的原坐标就是 b[i]。

两个细节:

  • 循环条件写 i < tot,因为最后一段的右端点是 tot,没有 tot + 1 这一段可加;
  • 答案要用 long long:坐标到 10^9,n 到 10^5,并集总长度可以到 2 \times 10^{14}。

参考代码

练习 5:逆序对

在线评测练习:P1473 逆序对

题目描述

给定 n 个整数,输出其中逆序对的数量。逆序对是指满足 i < j 且 a_i > a_j 的数对 (i, j)。

输入格式

第一行包含一个正整数 n。

第二行包含 n 个整数,相邻两个整数之间用一个空格隔开。

输出格式

输出一行一个整数,表示逆序对的个数。

数据范围

  • 1 \le n \le 10^5。
  • -10^9 \le a_i \le 10^9。

答案最大约为 n(n-1)/2,可能超出 int 范围。

输入输出样例

输入

4
3 2 1 4

输出

3

题目分析

这是上面「综合示例」的可提交版本,建议先自己写一遍再看代码。

它值得单独练,是因为它把离散化的必要性体现得最清楚:

  • 不离散化会怎样? 想用树状数组统计,下标就必须是 a_i 的值。a_i 到 10^9,数组开不下。
  • 离散化之后呢? 下标变成「排名」(1 \sim n),树状数组只需要 10^5 的空间。而逆序对只关心「谁比谁大」,不关心具体差多少,所以离散化是安全的——这正是本章判断标准那一条。

这道题对照本章的两个易错点:

  • 相同值不算逆序对。 题面写的是严格大于(a_i > a_j)。代码里用 query(rk) 取「排名 \le rk 的个数」再拿总数减,等于「严格大于它的个数」,相同值自然被排除。如果写成 query(rk - 1) 再减,就变成「大于等于」,答案会多出来。
  • 答案必须 long long。 逆序对最多约 n(n-1)/2 \approx 5 \times 10^9,超出 int(约 2.1 \times 10^9)。题面「可能超出 int 范围」就是在提醒这一点。

query(tot) - query(rk) 里的 query(tot) 就是「目前已扫过的元素总数」,因为它查询的是排名 \le tot 的个数,而所有元素排名都不超过 tot。这样写不依赖循环变量 i,含义比 (i-1) - query(rk) 更直白。

参考代码

练习 6(挑战):排名并列(竞赛排名)

在线评测练习:P1510 并列留空的竞赛排名

题目描述

给定 n 名选手的得分,按得分从高到低排名。得分相同的选手名次相同,且并列之后会留空名次(例如得分 100,90,90,80 的名次是 1,2,2,4)。

请按输入顺序输出每名选手的名次。

输入格式

第一行包含一个整数 n。

第二行包含 n 个整数,表示每名选手的得分,相邻两个整数之间用一个空格隔开。

输出格式

输出一行 n 个整数,按输入顺序给出每位选手的名次,相邻两个整数之间用一个空格隔开。

数据范围

  • 1 \le n \le 10^5。
  • |得分| \le 10^9。

输入输出样例

输入

4
100 90 90 80

输出

1 2 2 4

输入

5
50 50 50 100 30

输出

2 2 2 1 5

题目分析

这道题把离散化用在排名计算上,但它和练习 1 有一个关键区别:练习 1 的排名是「第几小」,本题要的是「第几大」,而且并列要留空名次。

第一步:把「第几大」换成「第几小」。 本章的三步做法给出的是升序排名 r(1 \sim tot)。降序名次不好直接二分出来(lower_bound 只能找升序位置),但可以做一步换算:升序排名第 r 小,就是升序排名第 tot - r + 1 大。这样完全不用改 lower_bound 的方向。

第二步:并列留空,不能简单换算。 这一步是本题的核心,也是本章易错点里那条「并列排名直接用『不同值个数 − 排名 + 1』」的正面教材。以样例 100 90 90 80 为例,升序去重后是 [80, 90, 100],tot = 3。如果直接用 tot - r + 1:

  • 100 → r = 3 → 名次 1 ✓
  • 90 → r = 2 → 名次 2 ✓
  • 80 → r = 1 → 名次 3 ✗(正确答案是 4)

错在 90 有两个人,占掉了名次 2 和 3,所以 80 只能是 4。差别就在「不同值的个数」与「元素的个数」之间——本章易错点专门强调过这一点。

正确公式:名次 = 严格比它大的元素个数 + 1。 注意是「元素」不是「不同值」。

第三步:用计数数组 + 倒扫(后缀和)算出这个公式。 离散化之后开一个 cnt[r] 统计每个排名的出现次数,然后从最高的排名往低扫,边扫边累加:

int sum = 0;
for (int r = tot; r >= 1; r--) {
  rankOfValue[r] = sum + 1;  // 比它大的元素有 sum 个
  sum += cnt[r];
}

走一遍样例 1:tot = 3,cnt[3] = 1(100)、cnt[2] = 2(90 两个)、cnt[1] = 1(80)。

  • r = 3(100):sum = 0 → 名次 1;sum = 1
  • r = 2(90):sum = 1 → 名次 2;sum = 4
  • r = 1(80):sum = 4 → 名次 4 ✓

样例 2 50 50 50 100 30 同理:去重后 [30, 50, 100],cnt 为 1、3、1,倒扫得到 100→1、50→2、30→5,输出 2 2 2 1 5 ✓

这个「倒着扫前缀和」就是后缀和,和前缀和是同一个思路、方向相反。得到 rankOfValue 之后,再按输入顺序二分查一次排名、查表输出即可。

参考代码

小结

离散化解决的是「值域很大、但真正出现的值很少」这一类问题,本质是把数值换成排名,让数组下标够用。

  • 口诀:排序、去重、二分。总复杂度 O(n \log n)。
  • 它只保留相对大小。题目一旦要算真实差值或距离,就得额外保留每个下标对应的原坐标。
  • 它很少单独使用,通常是差分、计数、树状数组、线段树的前置步骤。

学完这一章,下面这些事应该能独立完成:

  • 写出排序、去重、二分三步的离散化代码,并说清 lower_bound 得到的排名为什么就能当新下标。
  • 说出离散化的两个前提:只关心相对大小、原值可以回查。
  • 用离散化加差分解决坐标到 10^9 的区间覆盖问题。
  • 说清什么时候不能直接压缩:题目需要真实差值、或者需要判断两个值之间还夹着其他可能取值时。
  • 说出「离散化加树状数组求逆序对」的大致思路,并写完整代码。
  • 用离散化算并列留空的排名:名次 = 严格比它大的元素个数 + 1,用计数数组倒扫(后缀和)求出。
  • 分清「不同值的个数」和「元素的个数」——排名题里最常混淆的一处。
Navigation

Type to search…

↑↓ navigate↵ selectEsc close