核心逻辑与数学原理
离散化是一种保序的空间压缩技术。其物理本质是将无限或极大的稀疏值域，映射到有限且连续的紧凑值域，同时保持原数据的偏序关系不变。
在多数信息学竞赛题中，空间复杂度或辅助数据结构（如树状数组、线段树、桶）的开销直接取决于值域大小 $U$。若 $U \le 10^9$ 但实际有效空间点数 $N \le 10^5$，直接开辟空间会导致内存爆栈（MLE）。观察发现，算法的核心逻辑往往只关注元素之间的相对大小（即大于、小于、等于的偏序关系），而不关心其绝对数值。
通过建立单射映射 $f(x) \to k$，其中 $x$ 为原稀疏值域中的元素，$k \in [1, M] \, (M \le N)$ 为连续的正整数。该映射必须满足：
$$\forall x_i, x_j, \quad x_i < x_j \iff f(x_i) < f(x_j)$$
通过此技术，可以将空间复杂度从 $O(U)$ 强行打压至 $O(N)$，时间复杂度通常引入排序常数 $O(N \log N)$。
算法推导与映射构建
离散化的核心在于去重与二分检索。整体构建分为三个严格的拓扑步骤：
1. 离散化集合收集
将所有可能影响答案的绝对数值（包括查询边界、修改点等）全部压入一个动态数组 alls。集合大小为 $N$。
2. 排序与去重（Unique）
对 alls 进行升序排列，使数据具备单调性。随后利用双指针剔除重复元素，保证映射的唯一性。排序复杂度为 $O(N \log N)$，去重复杂度为 $O(N)$。去重后集合实际大小为 $M \, (M \le N)$。此时，数组下标 $i \in [0, M-1]$ 即为压缩后的新坐标。
3. 二分定位映射
对于任意原始大数值 $x$，在已构建的单调非递减序列 alls 中进行二分查找（std::lower_bound），求得第一个大于等于 $x$ 的迭代器位置。映射函数定义为：
$$f(x) = \text{lower\_bound}(\text{alls.begin}(), \text{alls.end}(), x) - \text{alls.begin}() + 1$$
加上 1 是为了将数据规整到 1-indexed 坐标系，全面兼容后续数据结构的边界处理。单次查询映射的时间复杂度为 $O(\log N)$。
C++ 标准源码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 封装离散化组件
struct Discretizer {
vector<int> alls;
// 添加待离散化的原始数值
void add(int x) {
alls.push_back(x);
}
// 执行绝对压缩，建立映射轨
void init() {
sort(alls.begin(), alls.end());
// unique 返回去重后的尾部迭代器，erase 彻底斩断尾部冗余内存
alls.erase(unique(alls.begin(), alls.end()), alls.end());
}
// 映射查询：将大值域单射到 [1, alls.size()]
int query(int x) {
// 关键点：lower_bound 依赖 init() 的单调性，否则直接死循环或返回错误迭代器
auto it = lower_bound(alls.begin(), alls.end(), x);
return (it - alls.begin()) + 1; // 转换为 1-indexed 坐标
}
// 获取离散化后的紧凑值域上限
int size() const {
return alls.size();
}
};
int main() {
// 关同步，斩断 IO 常数
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
if (!(cin >> n >> m)) return 0;
// 离散化不只是存原始数组，连同修改操作、查询操作的边界坐标必须一并压入
Discretizer d;
vector<pair<int, int>> adds(n);
for (int i = 0; i < n; ++i) {
cin >> adds[i].first >> adds[i].second;
d.add(adds[i].first);
}
vector<pair<int, int>> queries(m);
for (int i = 0; i < m; ++i) {
cin >> queries[i].first >> queries[i].second;
d.add(queries[i].first);
d.add(queries[i].second); // 致命踩坑点：区间的右边界必须一起离散化，否则查询时无法准确定位
}
// 激活压缩器
d.init();
// 建立紧凑值域的树状数组或差分数组
vector<long long> slots(d.size() + 2, 0);
// 模拟应用：单点加
for (const auto& op : adds) {
int pos = d.query(op.first);
slots[pos] += op.second;
}
// 前缀和预处理
vector<long long> sum(d.size() + 2, 0);
for (int i = 1; i <= d.size(); ++i) {
sum[i] = sum[i - 1] + slots[i];
}
// 模拟应用：区间查询
for (const auto& q : queries) {
int l = d.query(q.first);
int r = d.query(q.second);
cout << sum[r] - sum[l - 1] << "\n";
}
return 0;
}NOIP 实战避坑指南
- 漏记查询/修改边界导致二分越界或逻辑断裂
离散化最致命的错误是只对初始数组的坐标进行离散化，而忽略了后续在线修改（Modify）点坐标或区间查询（Query）的左边界 $L$ 和右边界 $R$。如果在init()阶段没有将 $L$ 和 $R$ 塞入alls数组，那么在执行query(R)时，lower_bound就会返回一个不属于原本偏序逻辑的递增位置，甚至返回alls.end()导致减出来的坐标发生超出辅助数据结构容量的越界访问，直接引发 Runtime Error（RE）或逻辑全面崩盘。 - 去重（Unique）前未排序引发的伪去重死循环
std::unique的底层实现机理是双指针扫描，它只会剔除相邻的重复元素。如果在调用unique之前没有调用std::sort保证序列绝对单调，乱序序列中的相同元素将无法被剔除。这会导致alls数组中依旧存在大量重复项，破坏了单射的唯一性。在随后的二分查找中，lower_bound算出来的紧凑坐标会发生严重偏移，导致算法产生极其隐蔽的逻辑错误。
经典 NOIP/洛谷 真题
1. 洛谷 P1496 火烧赤壁
- 题意描述：给定 $N$ 个闭区间 $[A_i, B_i]$，求这些区间的并集总长度。区间端点范围 $[-2^{31} \le A_i, B_i \le 2^{31}-1]$，$N \le 2 \times 10^4$。
- 问题本质：大值域一维区间覆盖总长度统计。
- 核心解题思路：
绝对坐标值域达到 $4 \times 10^9$，无法直接开布尔数组进行标记。但 $N$ 极小，所有的区间端点数至多有 $2N = 4 \times 10^4$ 个。将所有 $A_i$ 和 $B_i$ 收集进行离散化，建立紧凑坐标轴。在紧凑轴上利用差分数组标记每个被覆盖的网格。最后从左到右扫描紧凑轴，若当前网格被覆盖（差分前缀和大于 0），则将原绝对坐标的差值（即alls[i] - alls[i-1]）累加到答案中。成功将大值域区间并问题转化为 $O(N \log N)$ 的扫描线基准模型。
2. 洛谷 P1908 逆序对
- 题意描述：给定一个长度为 $N$ 的序列 $A$，求序列中满足 $i < j$ 且 $A[i] > A[j]$ 的数对 $(i, j)$ 的总量。$A[i] \le 10^9, N \le 5 \times 10^5$。
- 问题本质：动态值域前缀和计数。
- 核心解题思路：
标准解法是使用树状数组维护每个数值出现的频次，从左到右遍历元素，边查询大于当前数的个数边插入。但由于 $A[i]$ 达到 $10^9$，树状数组无法开到如此大的体量。
由于逆序对只取决于元素之间相对的偏序大小关系，与绝对值无关。将整个序列 $A$ 复制一份进行离散化预处理，将每个 $A[i]$ 单射替换为 $[1, N]$ 之间的正整数。随后，直接建立一个大小为 $N$ 的树状数组，遍历离散化后的新序列，利用query(N) - query(new_A[i])获取当前逆序贡献并累加，再执行update(new_A[i], 1)。时间复杂度 $O(N \log N)$，空间复杂度 $O(N)$。