离散化

介绍

要使用计数存储时（如把值作为数组下标），如果值域过大，则需要对其进行离散化处理，映射到更小值域。

原理

原值域中的一段连续相同区间，可合并为一个离散点，或只有部分值有意义。

• 建立 $原值域 \leftrightarrow 离散化值域$ 的映射关系
• 每个离散节点表示一个原值域的子集（区间）

原值域	1	…	80	81	…	114514
离散化值域	0	-	1	2	-	3
表示区间	1 ~ 80		80	81~114514		114514

步骤

• 收集原始数据到 all 数组
• 对 all 数组排序、去重（也有时不去重）
• 二分查找原值在 all 数组中下标，即为离散化值

代码

// 读入原始数据
vector<int> a(n), b(n), all;
for(int i = 0; i < n; i++){
    cin >> a[i] >> b[i];
    // 加入 all 数组
    all.push_back(a[i]);
    all.push_back(b[i]);
}
// 排序
sort(all.begin(), all.end());
// 去重
all.erase(unique(all.begin(), all.end()), all.end());
// 寻找下标
int m = all.size();
vector<int> shrinkA(m), shrinkB(m);
for(int i = 0;i < n;i++){
    shrinkA[i] = lower_bound(all.begin(), all.end(), a[i]) - all.begin();
    shrinkB[i] = lower_bound(all.begin(), all.end(), b[i]) - all.begin();
}