离散化是将大范围稀疏数值映射为紧凑连续小整数并保持大小顺序，常用保序（排序+去重+lower_bound）和不保序（unordered_map编号）两种方式，关键在确保所有相关值均被纳入映射集合。
离散化不是“把数组变小”，而是把大范围、稀疏的数值映射成紧凑、连续的小整数，同时保持大小顺序不变。它常用于树状数组、线段树、坐标压缩等场景——只要你想用数值当数组下标，但原始值太大（比如 1e9），就得离散化。
保序离散化：排序 + 去重 + 二分查找
这是最常用、最稳妥的方式，适合需要保留相对大小关系的场合（如求逆序对、区间统计）。
-
sort()后必须接unique()，但注意unique()不真删元素，只是把重复项移到末尾，返回的是第一个重复元素的迭代器/指针 - 计算去重后长度时，别写成
unique(...) - begin就完事——要减去起始地址再减 1，例如：int m = unique(b+1, b+n+1) - b - 1; - 映射用
lower_bound()最安全；手写二分时，边界初始化要一致（l=0, r=alls.size()-1或l=1, r=m），返回值是否 +1 取决于你想要从 0 还是 1 开始编号 - 示例关键片段：
vector<int> alls = nums;<br>sort(alls.begin(), alls.end());<br>alls.erase(unique(alls.begin(), alls.end()), alls.end());<br>for (int &x : nums) {<br> x = lower_bound(alls.begin(), alls.end(), x) - alls.begin() + 1;<br>}
不保序离散化：用 unordered_map 按首次出现顺序编号
当你只关心“不同值有多少个”，不依赖大小顺序（比如给每种颜色分配 ID、统计唯一事件类型），这种更快、更直白。
- 时间复杂度平均
O(n)，但哈希表有常数开销，且不保证顺序；多次运行结果可能不稳定（虽然对功能无影响） - 不能用
map代替unordered_map——前者自动排序，会悄悄变成保序，还慢 - 务必在
get()函数里检查mp.count(x)或直接用mp[x]（后者会默认构造 0，需手动判零或用try_emplace） - 示例：
unordered_map<int, int> mp;<br>int id = 0;<br>auto get = [&](int x) {<br> if (!mp.count(x)) mp[x] = ++id;<br> return mp[x];<br>};<br>for (int &x : nums) x = get(x);
常见坑：unique 和 lower_bound 的边界细节
这两个函数配合出错率极高，尤其在 1-indexed 场景下。
立即学习“C++免费学习笔记（深入）”；
-
unique(v.begin(), v.end())返回的是迭代器，擦除要用v.erase(..., v.end())，漏掉v.end()会导致后续访问越界 -
lower_bound查不到时返回v.end()，如果没提前确保x一定在alls中（比如输入数据未校验），解引用会崩溃 - 数组下标从 1 开始？那
alls排序前别 push_back(0)，也别让lower_bound返回 0——加 1 是为了避开 0 下标，但前提是所有原始值都合法存在于alls - 如果原数组含负数、0、极大正数，
alls必须包含全部，不能只处理一部分——漏掉某个值，映射就失效
真正麻烦的不是写几行代码，而是确认「哪些值必须进 alls」：操作中所有可能出现的数值（包括查询区间的端点、修改的坐标、甚至中间计算结果），一个都不能少。否则离散化后查不到，整个逻辑就断了。
