离散化本质是映射，即将稀疏原始值压缩为从0或1开始的连续整数序列；需先收集所有待离散值（含查询点、端点等），排序去重后用lower_bound查坐标，二维需分别处理x、y并独立建映射。
离散化本质是映射，不是排序
离散化真正要解决的，是把一堆稀疏、可能极大（比如 1e9）或带负数的原始值，压缩成紧凑、从 0 或 1 开始的连续整数序列。它不依赖排序本身，但排序是最常用手段——因为只有排好序，才能去重 + 建立下标到值的映射关系。
常见错误是只做 sort + unique，却忘了用 lower_bound 把原值“查回去”。没这一步，离散化就只是扔掉了重复值，没完成坐标压缩。
- 必须先收集所有待离散的值（包括查询点、端点、修改位置等），不能只对输入数组操作
- 用
vector存原始数据，sort后调用unique返回新尾迭代器，再用erase真删除 - 每次查找用
lower_bound(v.begin(), v.end(), x) - v.begin()，结果就是压缩后的坐标
std::lower_bound 的边界行为必须确认
离散化后坐标从 0 开始，但如果你的原始数据里有比最小值还小的数（比如查询时传入非法值），lower_bound 会返回 v.begin()，减出来是 0 —— 这看起来像合法坐标，实则越界。这不是 bug，是设计如此，你得自己兜底。
- 如果业务要求严格范围检查，查之前加
if (x v.back()) - 若允许“插入不存在的值”，那
lower_bound返回的下标就是它该在的位置，直接用没问题 - 别用
upper_bound替代，它返回的是第一个大于的下标，会导致相同值映射到不同坐标
重复值必须去重，但去重方式影响稳定性
离散化要求“相同原始值 → 相同压缩坐标”，所以去重不可省。但 unique 只移除相邻重复项，必须配合 sort 才生效；单独 unique 在未排序容器上等于白干。
立即学习“C++免费学习笔记（深入）”；
- 正确顺序：
sort(v.begin(), v.end()); auto it = unique(v.begin(), v.end()); v.erase(it, v.end()); - 不要用
set替代：虽然自动去重+有序，但插入复杂度高，且无法保证后续lower_bound查找效率（set不支持随机访问迭代器） - 若原始数据已部分有序（比如按时间戳追加），仍需全量
sort，不能只merge，否则unique会漏掉非邻接重复
二维坐标压缩要分别处理 x 和 y
遇到点集（如 vector<pair int>></pair>）需要压缩，不能把 x 和 y 拼成一个数再离散——比如 x=1000, y=2 和 x=10, y=200 可能哈希冲突。必须拆开，各自建映射表。
- 分别提取所有
x值到xs，所有y值到ys，各自排序去重 - 每个点
(x, y)映射为(lower_bound(xs.begin(), xs.end(), x) - xs.begin(), lower_bound(ys.begin(), ys.end(), y) - ys.begin()) - 注意：压缩后二维索引仍是稀疏的，不能直接开二维数组，要用
map<pair>, T></pair>或哈希表存
离散化最易被忽略的点，是“哪些值该进离散池”——漏掉查询中出现的坐标、区间端点、或者更新目标，压缩后查不到，程序就静默错。宁可多塞几个值，别省那几毫秒排序时间。