离散化
FLY_lai
·
·
个人记录
在问题中，我们经常需要把一些数放进下标里操作，如计数排序。
但是，如果问题的值域太大了，我们怎么办？（如 2 \times 10^9）
这个时候，就需要离散化。
【离散化】
我们可以把每一个数按顺序映射成一个比较小的数。
比如，a 数组是 2,10,1233,3242434
那么，映射之后就是：
这个映射的过程，就叫做离散化。
## 【实现】
法一：
### 排序
排序的作用，就是方便我们映射之后快速找到映射关系。
如果我们把所有数映射成了一个有序的连续整数序列，那查询一个数的位置就可以直接用二分查找，非常快捷。
### 去重
因为原数组中可能有重复元素，但是离散化的映射关系不可能一个数对应很多个数，所以要去重。
### 寻找
映射完之后，我们要找到原数所对应的映射值。因为已经排过序了，可以用二分查找。
法二：
用map把所有数记录下来，然后遍历一遍，map是自动从小到大遍历的。
法三：
排序，然后从前到后扫一遍，如果和前面不一样就 cur++ 然后赋值。
------------
我们发现，以上三步都可以用 STL 代替手写。
排序可以用 sort，去重可以用 unique，寻找可以用 lower_bound。
当然，如果有需要，可以自己手写以修改。
## 【板子】
法二：（最好写）
```
int a[N];
map<int, int> mp;
for (int i = 1; i <= n; i++) {
cin >> a[i];
mp[a[i]] = 0;
}
int cur = 0;
for (auto &i: mp)
i.second = ++cur;
for (int i = 1; i <= n; i++)
a[i] = mp[a[i]];
```