数据离散化与空间压缩 - NOI提高级教程

📖 算法原理：坐标去重与排序映射

在算法竞赛中，我们经常遇到数值范围极大（如 $X \in [-10^9, 10^9]$），但实际涉及的节点个数 $N$ 却极小（如 $N \le 10^5$）的区间问题。直接以数值作为数组索引开销是完全无法接受的。离散化（Discretization）通过映射，在保持元素原有大小相对大小关系的前提下，将所有大数值压缩成连续的较小数组索引 $[0, N-1]$。

📐 离散化去重与二分寻址法则

标准的 C++ 离散化流程包含三部曲：

排序收集：将所有需要使用的坐标放入一个一维容器 alls 中，执行 sort 升序排列。
去重压缩：利用 unique 割除重复元素，保留相对顺序，并擦除尾部垃圾地址。
二分映射（寻址）：利用 lower_bound 在 $O(\log N)$ 时间内，把原始值 $X$ 映射为其在去重排序后数组中的索引值。

💡 弹簧收缩的物理本质：离散化就如同给数轴装上高弹性弹簧。在保留节点左、中、右大小层级排序的前提下，将松散空洞的大刻度剔除，强力收缩并拢，使得相邻两项物理连续。

输入大坐标：

在上方文本框输入一个极其庞大的浮动数值（如 999999999），并点击“写入新坐标”添加至原始数轴，接着点击“开始离散化”观摩弹簧物理收缩！

🌪️ 超大数轴离散化物理收缩仪 (Discretization Shrinkage Axis)

📋 离散化映射散列卡片 (alls 映射表)

暂无映射。打入数值并点击“开始离散化”生成

vector<int> alls; // 存储所有超大离散坐标值

void discretize() {
    // 1. 升序排序
    sort(alls.begin(), alls.end());
    // 2. 去重，割除冗余元素
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
}

// 3. 二分查找获取离散化后紧凑的 0-indexed 索引
int find(int x) {
    return lower_bound(alls.begin(), alls.end(), x) - alls.begin();
}

📋 离散化物理收缩记录