---
title: "离散化"
description: "把大值域压缩成小下标，让数组和数据结构放得下。"
---

> Documentation Index
> Fetch the complete documentation index at: https://cppguide.xyz/llms.txt
> Use this file to discover all available pages before exploring further.

# 离散化

![](https://img.dailyup.xyz/optimized/8208353651465-7e412d35-42f0-47d5-a318-415878ae271f.jpg)

有些题目的数值范围大得离谱，坐标可以到 $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. **二分**。对每个原数，用二分查出它在去重数组里的位置，这个位置就是新的下标。

```cpp
#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)$ 且不需要离散化。两种做法都要会，比赛时归并排序更省事，而「离散化 + 树状数组」这个组合更能体现离散化的价值，也是后面学习二维偏序、动态逆序对的基础。

**参考代码**

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/algopatterns/discretization/index.md

几个要注意的点：

- **答案要用 `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 输出排名](https://dailyup.run/tasks/597)

#### 题目描述

给定 $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)$。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/algopatterns/discretization/index.md

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

在线评测练习：[P1478 各分数的人数](https://dailyup.run/tasks/562)

#### 题目描述

给定 $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` 防溢出），这就是离散化的价值：它把「值域大小」从复杂度里彻底拿掉了。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/algopatterns/discretization/index.md

### 练习 3：区间最大覆盖次数

在线评测练习：[P1512 区间最大覆盖次数](https://dailyup.run/tasks/596)

#### 题目描述

数轴上有 $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。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/algopatterns/discretization/index.md

### 练习 4（进阶）：区间并集的整数点个数

在线评测练习：[P1511 区间并集的整数点个数](https://dailyup.run/tasks/595)

#### 题目描述

数轴上有 $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}$。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/algopatterns/discretization/index.md

### 练习 5：逆序对

在线评测练习：[P1473 逆序对](https://dailyup.run/tasks/557)

#### 题目描述

给定 $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)` 更直白。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/algopatterns/discretization/index.md

### 练习 6（挑战）：排名并列（竞赛排名）

在线评测练习：[P1510 并列留空的竞赛排名](https://dailyup.run/tasks/594)

#### 题目描述

给定 $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]` 统计每个排名的出现次数，然后从最高的排名往低扫，边扫边累加：

```cpp
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` 之后，再按输入顺序二分查一次排名、查表输出即可。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/algopatterns/discretization/index.md

## 小结

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

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

学完这一章，下面这些事应该能独立完成：

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

Source: https://cppguide.xyz/algopatterns/discretization/index.mdx
