离散化
本文介绍了离散化算法，一种当数据范围巨大但实际使用的数据点较少时，通过压缩数据范围提升效率的算法。以洛谷 P1496 问题为例，展示了离散化的具体应用。文章详细阐述了离散化的步骤：收集所有区间端点，排序并去重得到离散化数组，然后通过二分查找将原区间映射到离散化数组的索引，最后进行统一计数。该算法的时间复杂度为 O(nlogn)，排序是主要瓶颈。文末提供了 C++ 实现代码，便于读者理解和实践。
本文介绍了离散化算法，一种当数据范围巨大但实际使用的数据点较少时，通过压缩数据范围提升效率的算法。以洛谷 P1496 问题为例，展示了离散化的具体应用。文章详细阐述了离散化的步骤：收集所有区间端点，排序并去重得到离散化数组，然后通过二分查找将原区间映射到离散化数组的索引，最后进行统一计数。该算法的时间复杂度为 O(nlogn)，排序是主要瓶颈。文末提供了 C++ 实现代码，便于读者理解和实践。