
有些题目的数值范围大得离谱,坐标可以到 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的下标,用树状数组或线段树处理。
反例也要记住:如果题目要算「两个坐标之间隔了多长」或者「面积是多少」,差值本身有意义,离散化时就得额外记录原坐标,否则会把距离压缩掉。
三步做法
- 排序。把所有需要离散化的数收集到一个数组里排好序。
- 去重。相同的值只保留一个,否则同一个值会映射到不同的下标。
- 二分。对每个原数,用二分查出它在去重数组里的位置,这个位置就是新的下标。
#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 \sim n); - 用树状数组维护每个排名出现过的次数:从左往右扫原序列,扫到
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 个端点处记录事件。
于是做法是本章三步的直接应用:
- 把全部
2n个端点(左右端点都收)排序去重; - 每个区间
[l, r]映射成压缩下标[l_i', r_i'],在d[l']++、d[r' + 1]--做差分; - 顺着压缩后的下标扫一遍前缀和,最大值就是答案。
为什么这里不需要保留原坐标? 因为题目只问「最多次数」,问的是次数而不是长度。次数在每一段里是常数,压缩掉距离不影响它。这和练习 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 的做法(只数「有多少段被覆盖」),会得到「被覆盖的段数」而不是「整数点个数」。因为两个相邻离散点之间可能隔着成百上千个整数点,压缩之后这些点全被压成了一个下标。这对应易错点里那两条:「压缩后直接算差值」和「把压缩后的排名当成原值」。
正确做法:
- 把闭区间
[l, r]改写成左闭右开[l, r+1)。这一步很关键——它让「闭区间含全部整数点」变成「区间长度为点数」,避免了+1/-1的反复纠结; - 把
l和r + 1都收进离散化数组(注意此时收的是R1 = r + 1,不是r); - 差分后从
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 = 1r = 2(90):sum = 1→ 名次 2;sum = 4r = 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,用计数数组倒扫(后缀和)求出。
- 分清「不同值的个数」和「元素的个数」——排名题里最常混淆的一处。