C++离散化技术详解：从原理到实战，解决大数据范围难题-拓冰建站

1. 项目概述

在算法竞赛和数据处理领域，我们经常会遇到一个看似简单却令人头疼的问题：数据范围太大。比如，你手头有一组坐标数据，[1, 1000000000, 500, 1000000000, 999999999]，你想用它们作为数组下标来统计频率，或者构建线段树、树状数组。直接开一个大小为10亿的数组？内存会立刻爆炸。但仔细一看，虽然数值很大，但实际不同的值只有4个（1， 500， 999999999， 1000000000）。离散化（Discretization）正是为了解决这类“数值大、种类少”的矛盾而生的核心技术。

简单来说，离散化就是将无限空间或大空间中的有限个体，映射到有限、连续的小空间中去。它不关心数据的绝对大小，只关心数据之间的相对顺序关系。经过离散化处理后，原本稀疏、分散的数值被压缩成紧密、连续的整数序列（通常是1, 2, 3, ...），从而使得我们可以用常规的数据结构（如数组、线段树）高效地处理这些数据。这就像给一群身高各异的人按照从矮到高排队并发放连续的号码牌，之后我们只需要操作他们的号码，就能知道谁高谁矮，而无需记住他们具体的身高。

掌握离散化，是解决众多区间问题、统计问题、以及优化空间复杂度的关键一步。无论是处理用户ID、地理坐标、时间戳，还是优化动态规划的状态空间，离散化都是一把利器。接下来，我将结合十多年的编码经验，为你彻底拆解C++中离散化的核心原理、多种实现方法、易错细节以及实战应用。

2. 离散化的核心思想与价值解析

2.1 为什么需要离散化？

离散化解决的痛点非常明确：空间与效率的冲突。

假设你正在处理一个“区间染色”问题：有10^5个操作，每个操作给一个区间[L, R]涂上一种颜色，L和R的取值范围是[-10^9, 10^9]。最后需要查询某个点被涂了几次颜色。

一个朴素的想法是开一个大小为2 * 10^9的数组来模拟数轴，但这在内存上完全不可行。然而，观察发现，虽然坐标范围巨大，但所有操作涉及到的关键点（每个区间的左右端点）最多只有2 * 10^5个。这些关键点才是影响最终结果的“事件点”。离散化的精髓就在于，我们只关心这些关键点之间的相对位置关系，而不关心它们具体的、巨大的绝对值。

通过离散化，我们将这最多20万个关键点映射到[1, 2*10^5]这个连续的整数区间内。之后，所有的区间操作和点查询，都可以在这个压缩后的、稠密的新坐标体系下进行，使用差分数组、线段树等数据结构就能轻松搞定，空间复杂度从O(范围)降到了O(关键点数量)。

2.2 离散化的本质：保序映射

离散化不是一个随意的压缩过程，它必须满足一个核心性质：保序性。即对于原序列中的任意两个元素a和b：

如果a < b，那么离散化后a映射的值也小于b映射的值。
如果a == b，那么离散化后a和b映射的值相同（在去重离散化中）或遵循特定规则（在不去重离散化中）。

这个性质保证了离散化后的新序列，完全保留了原序列元素之间的大小关系。所有基于大小比较的算法（如二分查找、排序、树状数组求逆序对）在离散化后依然成立。

2.3 两种主要的离散化场景

在实际应用中，离散化主要分为两大类，对应着两种不同的需求：

去重离散化（值映射）：这是最常见的形式。将原数组中所有不同的值，按照从小到大的顺序，依次映射为1, 2, 3, ...。它常用于将数据值本身作为“键”（Key）的场景，比如统计某个值的出现次数、作为线段树的下标等。核心是“值”到“排名”的映射。
保序离散化（坐标压缩）：不仅保留值的大小关系，有时还需要保留相同值出现的先后顺序信息。例如，在求逆序对时，如果数组中有重复元素，我们需要明确哪个出现在前，哪个出现在后。这时，离散化映射需要保证：若a == b且a在原数组中位置在b之前，则a映射的值小于b映射的值。核心是“值+位置”到“唯一ID”的映射。

理解这两种场景的区别，是正确实现和应用离散化的前提。下面我们将深入这两种场景的具体实现。

3. 去重离散化的标准实现与细节剖析

去重离散化是最经典的模式，其目标是将所有不同的数值映射为一个连续的整数序列。标准实现通常遵循“排序、去重、二分查找”三步法。

3.1 标准三步法实现

假设我们有一个原始数组vector<int> arr，包含n个元素。

#include <vector> #include <algorithm> using namespace std; // 假设原始数据 vector<int> arr = {1000, -500, 0, 1000, 500, -500}; // 第一步：复制并排序 vector<int> tmp = arr; // 创建副本 sort(tmp.begin(), tmp.end()); // 第二步：去除重复元素 // unique将重复元素移到容器末尾，并返回指向第一个重复元素的迭代器 // erase删除从该迭代器到末尾的所有元素 tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end()); // 第三步：为每个原始元素查找其排名（离散化后的值） vector<int> discrete_arr(arr.size()); for (int i = 0; i < arr.size(); ++i) { // lower_bound 返回第一个 >= arr[i] 的迭代器 // 减去 begin() 得到下标，从0开始。+1可使其从1开始（常用于树状数组等） discrete_arr[i] = lower_bound(tmp.begin(), tmp.end(), arr[i]) - tmp.begin() + 1; } // 此时： // tmp = [-500, 0, 500, 1000] (排序去重后的唯一值列表) // discrete_arr = [4, 1, 2, 4, 3, 1] (原始数组映射后的结果，从1开始编号)

关键点解析：

std::unique的行为：它并不会“删除”元素，而是将不重复的元素移动到容器前部，并返回一个指向新的逻辑末尾（第一个重复元素位置）的迭代器。真正的删除需要配合erase完成。它的去重是基于“相邻重复”，所以必须先排序。
std::lower_bound的作用：在已排序的tmp中，二分查找第一个不小于目标值arr[i]的位置。由于tmp包含了所有可能的值，且arr[i]一定存在于tmp中，所以这个查找一定能成功，并且返回的位置就是arr[i]在tmp中的排名（下标）。
下标从1开始：+1操作是常见技巧。许多数据结构（如树状数组、线段树的递归实现）使用1-based索引更为方便，可以避免下标0带来的边界判断麻烦。

3.2 使用`map`或`unordered_map`的替代方案

对于去重离散化，我们也可以使用关联容器一次性完成映射：

vector<int> arr = {1000, -500, 0, 1000, 500, -500}; vector<int> tmp = arr; sort(tmp.begin(), tmp.end()); tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end()); unordered_map<int, int> mapping; // 或 map for (int i = 0; i < tmp.size(); ++i) { mapping[tmp[i]] = i + 1; // 建立值到排名的映射 } vector<int> discrete_arr(arr.size()); for (int i = 0; i < arr.size(); ++i) { discrete_arr[i] = mapping[arr[i]]; }

方案对比：

lower_bound二分法：时间复杂度O(n log n)（排序） +O(n log n)（n次二分查找）。空间复杂度O(n)。优点是不需要额外的哈希表，缓存友好。
map映射法：时间复杂度O(n log n)（排序和map插入）。空间复杂度O(n)。代码更直观，但map本身有开销。unordered_map平均O(n)，但最坏情况O(n^2)，且在竞赛中可能被卡常数。

实操心得：在绝大多数算法竞赛和工程场景中，排序+去重+二分的方案是首选。它稳定、高效，且不依赖于哈希函数的性能。map方案在需要频繁通过原值查询离散化结果时（即反向映射rank -> value也很频繁）可能更方便，但这种情况较少。

3.3 处理特殊数据类型：浮点数与字符串

离散化的对象不限于整数。只要数据类型支持比较（定义<运算符），就可以离散化。

浮点数离散化：方法与整数完全一致。但需要注意浮点数的精度问题。如果两个浮点数在数学上相等，但由于计算误差导致有微小差别，std::unique可能无法正确去重。在这种情况下，可能需要自定义比较函数，当差值小于一个极小值eps时视为相等。

vector<double> arr = {3.14, 2.71, 3.1400000001, 2.71}; vector<double> tmp = arr; sort(tmp.begin(), tmp.end()); // 自定义去重逻辑（如果需要处理精度） auto it = unique(tmp.begin(), tmp.end(), [](double a, double b) { return fabs(a - b) < 1e-9; // 根据实际情况调整eps }); tmp.erase(it, tmp.end()); // ... 后续二分查找同理，可能需要自定义比较器

字符串离散化：同样适用。std::string支持<运算符（按字典序比较），因此可以直接排序、去重、二分。

vector<string> arr = {"apple", "banana", "apple", "cherry"}; vector<string> tmp = arr; sort(tmp.begin(), tmp.end()); tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end()); vector<int> discrete_arr(arr.size()); for (int i = 0; i < arr.size(); ++i) { discrete_arr[i] = lower_bound(tmp.begin(), tmp.end(), arr[i]) - tmp.begin() + 1; }

4. 保序离散化（处理重复元素顺序）

在某些场景下，我们需要区分相同数值的不同出现。例如，在计算逆序对时，数组[5, 2, 5, 1]。两个5是不同的元素。如果我们简单地去重离散化，两个5会被映射成同一个值，就无法正确计算它们与中间2构成的逆序关系。

这时，我们需要一种能保留原始顺序信息的离散化方法。核心思想是：将每个元素视为一个由“值”和“索引”组成的二元组，排序时，值小的在前；值相同时，原始索引小的在前。

4.1 结构体/`pair`实现法

这是最清晰的方法。我们为每个元素记录它的原始下标idx和值val。

struct Node { int val; // 原始值 int idx; // 在原数组中的位置 // 重载小于运算符：先按值排序，值相同按索引排序 bool operator<(const Node& other) const { if (val != other.val) return val < other.val; return idx < other.idx; } }; vector<int> arr = {5, 2, 5, 1}; int n = arr.size(); vector<Node> nodes(n); for (int i = 0; i < n; ++i) { nodes[i] = {arr[i], i}; } // 排序 sort(nodes.begin(), nodes.end()); // 离散化赋值：排序后的位置（从1开始）就是其新的“ID” vector<int> discrete_arr(n); for (int rank = 0; rank < n; ++rank) { int original_index = nodes[rank].idx; discrete_arr[original_index] = rank + 1; // 排名作为新ID } // 结果：discrete_arr = [3, 2, 4, 1] // 解释：原数组[5(0), 2(1), 5(2), 1(3)] // 排序后：[1(3), 2(1), 5(0), 5(2)] // 排名： 1 2 3 4 // 按原始位置写回：[位置0得3, 位置1得2, 位置2得4, 位置3得1]

结果分析：可以看到，两个值同为5的元素，因为位置0在位置2之前，所以被赋予了不同的离散化值（3和4），并且位置0的5映射值小于位置2的5。这完美保留了原始的顺序信息。

4.2 利用`std::stable_sort`

我们也可以利用稳定排序的特性。先按值排序，对于值相同的元素，稳定排序会保持它们原有的相对顺序。然后我们按排序后的顺序赋予排名即可。

vector<int> arr = {5, 2, 5, 1}; int n = arr.size(); vector<int> index(n); iota(index.begin(), index.end(), 0); // 生成序列 0, 1, 2, ..., n-1 // 按arr的值对index进行排序，使用lambda比较arr的值 stable_sort(index.begin(), index.end(), [&](int i, int j) { return arr[i] < arr[j]; }); vector<int> discrete_arr(n); for (int rank = 0; rank < n; ++rank) { int original_index = index[rank]; discrete_arr[original_index] = rank + 1; } // 结果同上

这种方法避免了自定义结构体，代码更简洁。stable_sort保证了值相同时，原始索引小的仍然排在前面。

注意事项：std::sort是不稳定排序，不能保证值相等时元素的原始顺序。因此在这种场景下必须使用std::stable_sort或自定义比较函数。

5. 离散化的典型应用场景与实战解析

理解了原理和实现，我们来看看离散化在哪些地方大显身手。我将通过几个经典问题，展示如何将离散化作为关键步骤嵌入到解决方案中。

5.1 应用一：树状数组求逆序对

这是离散化最经典的应用之一。逆序对定义为i < j且a[i] > a[j]的数对。当数值范围很大时，无法直接开桶统计。

解题思路：

对原数组进行保序离散化，将数值映射到1~n的范围内。注意，这里必须用保序离散化（4.1或4.2节的方法），以区分相同的值。
从前往后（或从后往前）遍历离散化后的数组。
使用树状数组维护当前已遍历元素中，各个值出现的次数。
对于当前元素x，查询树状数组中[x+1, n]这个区间内已经有多少个数（即值比x大且已经出现过的数），这些数都与当前x构成逆序对（因为它们出现在x之前）。
将当前元素x插入树状数组（即x位置计数+1）。

#include <vector> #include <algorithm> using namespace std; class BIT { // 树状数组类 vector<int> tree; int n; public: BIT(int size) : n(size), tree(size + 1, 0) {} void update(int idx, int delta) { for (; idx <= n; idx += idx & -idx) tree[idx] += delta; } int query(int idx) { // 前缀和 [1, idx] int sum = 0; for (; idx > 0; idx -= idx & -idx) sum += tree[idx]; return sum; } int rangeQuery(int l, int r) { // 区间和 [l, r] if (l > r) return 0; return query(r) - query(l - 1); } }; long long countInversions(vector<int>& nums) { int n = nums.size(); // 1. 保序离散化 (使用结构体法) vector<pair<int, int>> val_idx(n); for (int i = 0; i < n; ++i) val_idx[i] = {nums[i], i}; sort(val_idx.begin(), val_idx.end()); // pair默认先比较first，再比较second vector<int> discrete(n); for (int rank = 0; rank < n; ++rank) { int original_idx = val_idx[rank].second; discrete[original_idx] = rank + 1; // 映射到1~n } // 2. 树状数组统计逆序对 BIT bit(n); long long ans = 0; for (int i = n - 1; i >= 0; --i) { // 从后往前遍历 int x = discrete[i]; // 查询当前元素前面(原数组顺序中，即i之前)有多少个数小于x // 由于我们从后往前，此时树状数组中存储的是原数组中i之后的所有元素 // 对于原数组中的j > i，如果a[j] < a[i]，则构成逆序对。 // 离散化后，就是值小于当前x的个数。 ans += bit.query(x - 1); // 查询[1, x-1]的个数 bit.update(x, 1); // 将当前元素插入 } // 另一种方向：从前往后遍历，查询比当前x大的数的个数 // BIT bit2(n); // long long ans2 = 0; // for (int i = 0; i < n; ++i) { // int x = discrete[i]; // ans2 += bit2.rangeQuery(x + 1, n); // 查询[x+1, n]的个数 // bit2.update(x, 1); // } // assert(ans == ans2); return ans; }

为什么必须用保序离散化？考虑数组[2, 2, 1]。有两个相等的2。如果简单去重，两个2映射为同一个值，那么计算逆序对时，第一个2和第二个2之间就不会被计入（因为值相等）。但实际上，在严格定义i<j且a[i]>a[j]中，相等的数不构成逆序对，所以这个例子中逆序对只有(2@idx0, 1)和(2@idx1, 1)，共2对。保序离散化将两个2映射为不同的值（如2和3），这样在树状数组查询时，第二个2（映射为3）不会认为第一个2（映射为2）比它“大”，从而得到正确结果0；同时它们对1的贡献能正确计算。如果简单去重，两个2都映射为2，计算逻辑会混乱。

5.2 应用二：区间染色与扫描线（矩形面积并）

这是离散化结合扫描线算法的经典问题。给定一堆矩形（用左下角和右上角坐标表示），求这些矩形覆盖的总面积。坐标范围可能很大（如-10^9 到 10^9），但矩形数量有限（如10^4个，产生约2*10^4个不同的x坐标）。

解题思路：

事件扫描：将每个矩形看作两条垂直的“线”：入边（下边）和出边（上边），每条线记录其x范围[x1, x2]和y坐标，以及是入边(+1)还是出边(-1)。
离散化x坐标：将所有矩形的x1和x2收集起来，去重排序。这样就将连续的x轴分割成了若干个离散的“竖条”。
垂直扫描：将所有边按y坐标排序，从下往上扫描。
线段树维护：用线段树维护当前扫描线覆盖的x轴区间。线段树的每个叶子节点对应离散化后相邻两个x坐标形成的区间[x_i, x_{i+1}]。节点信息存储该区间被当前扫描线覆盖的次数（cnt）以及该区间实际的长度（len，通过离散化坐标差值计算）。
面积累加：当从一条扫描线移动到下一条时，中间的高度差Δy乘以当前x轴被覆盖的总长度total_len，就是这一小段矩形条的面积，累加到答案中。

// 简化版核心代码，展示离散化与线段树结合 struct Edge { int x1, x2; // 离散化后的x坐标索引 int y; int flag; // +1 入边， -1 出边 bool operator<(const Edge& other) const { return y < other.y; } }; long long rectangleArea(vector<vector<int>>& rectangles) { vector<int> xs; // 收集所有x坐标 for (auto& rect : rectangles) { xs.push_back(rect[0]); // x1 xs.push_back(rect[2]); // x2 } // 1. 离散化x坐标 sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end()); int m = xs.size(); // 2. 构建扫描线事件 vector<Edge> edges; for (auto& rect : rectangles) { int x1 = rect[0], y1 = rect[1], x2 = rect[2], y2 = rect[3]; // 将实际x坐标映射为离散化后的索引 int idx1 = lower_bound(xs.begin(), xs.end(), x1) - xs.begin(); int idx2 = lower_bound(xs.begin(), xs.end(), x2) - xs.begin(); edges.push_back({idx1, idx2, y1, 1}); edges.push_back({idx1, idx2, y2, -1}); } sort(edges.begin(), edges.end()); // 3. 线段树定义 (维护区间覆盖次数cnt和有效长度len) vector<int> cnt(4 * m, 0); vector<long long> len(4 * m, 0); // 建树，初始化每个叶子节点对应的原始长度 (xs[i+1] - xs[i]) // ... (此处省略线段树建树代码) auto update = [&](int node, int l, int r, int ql, int qr, int val) { if (ql >= r || qr <= l) return; if (ql <= l && r <= qr) { cnt[node] += val; } else { int mid = (l + r) / 2; update(node*2, l, mid, ql, qr, val); update(node*2+1, mid, r, ql, qr, val); } // 向上更新len: 如果当前区间被完全覆盖，则长度为原始长度；否则为左右儿子长度和。 if (cnt[node] > 0) { len[node] = raw_len[node]; // raw_len 需预计算 } else { if (r - l == 1) len[node] = 0; else len[node] = len[node*2] + len[node*2+1]; } }; // 4. 扫描 long long ans = 0; long long prev_y = edges[0].y; for (int i = 0; i < edges.size(); ) { // 处理同一高度的所有边 int cur_y = edges[i].y; // 累加从prev_y到cur_y这一层的面积 ans += len[1] * (cur_y - prev_y); // len[1]是根节点维护的总有效覆盖长度 int j = i; while (j < edges.size() && edges[j].y == cur_y) { update(1, 0, m-1, edges[j].x1, edges[j].x2, edges[j].flag); ++j; } prev_y = cur_y; i = j; } return ans; }

离散化在这里的关键作用：将连续的、范围巨大的x坐标轴，压缩为m-1个小区间。线段树只需要管理O(m)个节点，而不是O(坐标范围)个节点，使得问题在时间和空间上都变得可行。

5.3 应用三：处理离线查询与前缀和优化

有一类问题，我们需要对多个区间[l, r]进行查询，例如“区间内不同数字的个数”。如果使用莫队算法，复杂度是O(n√n)。但如果我们允许离线处理，并且结合树状数组和离散化，可以达到O((n+q) log n)。

以“查询区间内不同数字个数”为例（SPOJ DQUERY）：

读入数组a，并将其值离散化（去重即可）。
读入所有查询(l, r)，按r排序。
维护一个树状数组bit，以及一个数组last[pos]，记录每个值上一次出现的位置。
从左到右遍历数组位置i（从1开始）：
- 如果当前值a[i]之前出现过（last[val] != 0），则在树状数组中将last[val]位置-1（撤销之前的贡献）。
- 在树状数组的i位置+1。
- 更新last[val] = i。
- 处理所有右端点r == i的查询：该查询的答案就是树状数组前缀和query(r) - query(l-1)，这个和代表了在[l, r]区间内，所有“最后一次出现位置”在[l, r]中的数字个数，即不同数字的个数。

// 核心思路伪代码 vector<int> a = {...}; // 原始数组 // 1. 离散化a的值 vector<int> tmp = a; sort(tmp.begin(), tmp.end()); tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end()); unordered_map<int, int> mp; for(int i=0; i<tmp.size(); ++i) mp[tmp[i]] = i+1; vector<int> discrete_a(a.size()); for(int i=0; i<a.size(); ++i) discrete_a[i] = mp[a[i]]; // 2. 读入查询，按r排序 vector<Query> queries = {...}; sort(queries.begin(), queries.end(), [](Query a, Query b){return a.r < b.r;}); // 3. 树状数组和last数组 BIT bit(n); vector<int> last(tmp.size()+1, 0); // 值域大小 vector<int> ans(queries.size()); int pos = 0; // 当前处理到的数组下标 for(auto &q : queries) { while(pos < q.r) { pos++; int val = discrete_a[pos-1]; // 假设1-indexed if(last[val] != 0) { bit.update(last[val], -1); } bit.update(pos, 1); last[val] = pos; } ans[q.id] = bit.query(q.r) - bit.query(q.l-1); }

离散化在此确保了last数组的大小与数字的种类数成正比，而不是与数字的最大值成正比，极大地节约了空间。

6. 常见问题、陷阱与性能优化

6.1 边界问题与下标处理

这是离散化最容易出错的地方。

下标从0开始还是从1开始？
- 从1开始：这是最推荐的做法。与树状数组、线段树等数据结构的常规用法保持一致，可以避免很多if (x==0)的判断。在lower_bound查找后+1即可。
- 从0开始：有时为了与C++标准库的迭代器风格统一（begin()对应0）。但要小心处理查询前缀和时的边界。
离散化后值域大小：离散化后的值域是[1, m]，其中m是去重后元素个数。在开数组（如树状数组、last数组）时，大小应为m+1或m+5以留有余地，而不是原始的n+1。
二分查找的边界：使用lower_bound时，确保查找范围是离散化后的有序数组tmp。lower_bound(tmp.begin(), tmp.end(), x) - tmp.begin()返回的是[0, m)的下标。如果你需要1-based，就+1。

6.2 去重与不去重的选择错误

这是概念性错误，会导致结果完全错误。

错误场景：在需要区分相同值不同位置的场景（如逆序对）使用了去重离散化。
正确做法：仔细分析问题本质。如果算法依赖于值的唯一性（如作为数组下标），用去重离散化。如果算法依赖于元素的唯一身份（即使值相同），用保序离散化。

一个简单的判断方法是：问自己“如果两个元素值相同，我希望它们在离散化后是同一个值还是不同的值？”

6.3 性能优化技巧

原地离散化：如果不需要保留原始数组，可以原地修改。

vector<int> arr = {...}; vector<int> tmp = arr; sort(tmp.begin(), tmp.end()); tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end()); for (int& x : arr) { // 注意是引用 x = lower_bound(tmp.begin(), tmp.end(), x) - tmp.begin() + 1; } // 现在arr里存储的就是离散化后的值

预先分配内存：在处理大量数据时，频繁的vector扩容会有开销。如果知道数据量n，可以预先reserve。
```
vector<int> tmp; tmp.reserve(n);
```

避免不必要的拷贝：如果原始数据很大，创建副本tmp会有内存和时间开销。有时可以记录索引进行排序。

vector<int> arr = {...}; vector<int> index(arr.size()); iota(index.begin(), index.end(), 0); sort(index.begin(), index.end(), [&](int i, int j){ return arr[i] < arr[j]; }); // 现在index是按arr值排序后的下标顺序 // 如果需要离散化后的数组，可以再创建一个结果数组并填充 vector<int> discrete(arr.size()); int rank = 1; for (int i = 0; i < index.size(); ++i) { if (i > 0 && arr[index[i]] != arr[index[i-1]]) rank++; discrete[index[i]] = rank; }

这种方法避免了复制整个arr，但代码稍复杂。

使用数组代替vector：在性能极其关键的场合（如竞赛），如果数据规模固定，使用C风格数组可能比vector稍快，因为少了动态分配的开销。但牺牲了安全性和便利性。

6.4 离散化与哈希表的权衡

什么时候用离散化，什么时候直接用unordered_map？

离散化：适用于需要顺序性的操作，如区间查询、前缀和、树状数组、线段树，或者后续步骤需要依赖排序后的顺序。离散化后的值是连续的整数，可以作为数组下标，访问效率是O(1)，且缓存友好。
unordered_map：适用于单纯的“键-值”映射，且不需要顺序遍历或基于顺序的查询。当键的范围极度稀疏，且离散化后数组仍然很大时，unordered_map可能更省内存。但它的访问是O(1)平均，最坏O(n)，且常数较大。

经验法则：如果后续算法需要用到数组下标来快速访问（尤其是结合树状数组、线段树），或者需要处理区间和顺序问题，优先选择离散化。如果只是简单的计数、存在性检查，且键的种类非常多，可以考虑unordered_map。

离散化是算法工具箱中一件朴实但威力巨大的工具。它通过将问题从“值域空间”转换到“索引空间”，巧妙地绕开了大数据范围的限制。理解其保序的本质，熟练掌握去重和保序两种模式的实现，并能在树状数组、线段树、扫描线等场景中灵活运用，是提升算法解决能力的关键一步。在实际编码中，多思考一步“这个场景需要去重吗？”，处理好下标边界，你就能避开大多数陷阱，让离散化成为你解决复杂问题的得力助手。