离散化

离散化主要用于将一个可能[HTML_REMOVED]非常大或稀疏的数列映射到一个较小的、连续的整数范围内[HTML_REMOVED]，从而方便处理和优化。例如，原本的数列值可能在一个非常大的范围内分布，而离散化可以将其压缩到一个相对较小的范围内，以便在数组或其他数据结构中使用。

以下是实现离散化的一般步骤：
1. 收集并排序所有要离散化的数值：
- 首先将所有要进行离散化的元素收集到一个容器中（如 vector）。
- 然后对这些元素进行排序，并去重，得到唯一值的排序数组。
2. 建立原值到离散化后值的映射：
- 通过二分查找（使用 lower_bound）来建立原始值到离散化后的整数值的映射。
3. 应用离散化：
- 使用映射将原始数据转换为离散化后的数据。

vector<int> alls; // 存储所有待处理点

sort(alls.begin(), alls.end()); // 排序
alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 去重

// 用find()寻找映射值
int find1(int x){ // 用二分法, 找到第一个大于等于x的位置
    int l = 0, r = alls.size() - 1;
    while(l < r){
        int mid = l + r >> 1;
        if(alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1; // 映射到1, 2, 3, ...
}

int find2(int x){ // 用 lower_bound(), 找到第一个大于等于x的位置(其实也是二分)
    return lower_bound((alls.begin(), alls.end()), x);
}