离散化（坐标压缩）

离散化将稀疏且跨度巨大的数值映射为连续编号，同时保持相对大小：若 x<y，则 id(x)<id(y)。当只关心顺序、却需要数组下标、树状数组或并查集时，它能避免按原值域分配内存。

标准流程

先收集所有可能使用的值（包括更新值和查询端点），再排序、去重，并用二分查找原值的排名。预处理 O(n log n)，每次映射 O(log n)。

vector<long long> xs;
// 收集所有坐标后：
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
auto id = [&](long long x) {
    return int(lower_bound(xs.begin(), xs.end(), x) - xs.begin()) + 1;
};

unique 只把不重复元素移到前段并返回新的逻辑末尾，必须配合 erase 才能真正删去尾部。离散化前未知的数据通常先离线读入并收集，再统一处理。

边界与区间

若查询端点保证出现，直接映射即可；端点不一定出现时，应根据语义使用 lower_bound 找第一个不小于目标的位置，或用 upper_bound 找第一个大于目标的位置。普通离散化只保序，不保留原坐标间的距离。

扫描线、矩形面积并和周长并等区间问题应保存原坐标：压缩后的第 i 段真实长度由 xs[i+1]-xs[i] 计算。视题意还可能需要收集相邻位置或将区间拆成坐标段，不能把编号之差误作真实长度。

典型结合与错误

离散后的编号可作为树状数组、线段树、并查集的索引，用于逆序对、区间统计、扫描线和离线查询。常见错误是漏收集更新或查询端点、忘记 erase(unique(...))、混用 0/1 下标，以及在未确认值存在时直接将 lower_bound 结果当作精确映射。