离散化介绍

离散化，就是将一组离散的数据，映射成集中的数据。【所以个人觉得应该叫集中化【？……
其思想跟哈希(Hash)类似。

当有些数据因为本身很大或者类型不支持，自身无法作为数组的下标来方便地处理，
而影响最终结果的只有元素之间的相对大小关系时，
我们可以将原来的数据按照从大到小编号来处理问题，即离散化。

引自：OI-Wiki「离散化」

常用来离散化类型的是：大整数、浮点数、字符串。

情况举例

本身很大情况

最常见的题比如：

判断在$N$个数中，某数$a_i$是否存在。

很简单的思路就是：
用个布尔数组bool exist[]来记录某数是否存在。

但如果数据范围是$1 \le N \le 10^5, 0 \le a_i \le 10^9$，
也就是：数的个数$N$远小于数的范围$a_i$时，
很明显，如果直接用$a_i$作下标来记录，会导致数组开不下。

而对于这道题，$a_i$的值是多少，并没有太大意义，我们只用关心它出现没有。
因此我们可以把这些分散的$a_i$按大小顺序重新编号。

举例

5个数，其分别为：

9463 1 233333333 78 5

此时如果直接以下标来存储，数组就要开为bool exist[233333333 + 5];。

将其重新编号（映射）为：

4 1 5 3 2

此时数组就可以开为bool exist[5 + 5];。

类型不支持情况

将题改为：

$N$个字符串，判断某字符串$s_i$是否存在。

这个时候甚至直接不能作为bool exist[]数组下标了。

可以将其映射为能作为下标的数字。

要查找某字符串，用该映射函数将所寻字符串映射为数字ID，
然后直接看exist[ID]是否为$true$即可。

实现方法

思路

上面介绍说到：离散化后的数据只与相互间大小关系有关。
所以对于原数据要先放在另一个容器中排序，得到他们之间的大小关系。

然后该容器中需要去除重复元素，来最大程度节省空间。

比如原数据为$100$个$8$和$1$个$9$。

如果不去重，离散化后$8$会映射为$1$，而$9$会映射为$101$，
去重过后，$8$会映射为$1$，$9$则会映射为$2$了。

这样过后便得到了原数据与新数据的一一映射关系表。
这个时候再将原数据按表全部替换，完成离散化。

所以离散化一共有三个重要操作：

对原数据放到另一个容器，并按大小关系排序。
去除排好序后容器的重复元素，得到一一映射关系。
按照一一映射关系，将原数据替换为新数据。

举例

原数据为：

98 783 1 23333 1 57 912 5 1 98

排序后为：

1 1 1 5 57 98 98 783 912 23333

去重后为：

1 5 57 98 783 912 23333

则得到一一映射关系表：

原数据	新数据
1	1
5	2
57	3
98	4
783	5
912	6
23333	7

替换后，即离散化为：

4 5 1 7 1 3 6 2 1 4

具体实现

一、大整数离散化

去重操作使用到的是unique函数，
映射关系表对应，则用lower_bound这个查找函数。

有关这两个函数的详细信息，可以百度查阅相关资料。

代码：

int raw[MAX_N + 5],  //原数据
    n,               //原数据个数
    cont[MAX_N + 5], //临时容器
    disc[MAX_N + 5]; //离散化后数据

void discrete()
{
    memcpy(cont, raw, (n + 1) * sizeof(int)); //1. 原数据放入另一容器
    sort(cont + 1, cont + n + 1);             //1. 排序

    int disc_len = unique(cont + 1, cont + n + 1) - cont - 1; //2. 去重，并得到去重后的有效长度（运用的是数组地址相减代表长度）。

    for (int i = 1; i <= n; i++)                                             //3. 按照一一映射关系，得到离散化序列
        disc[i] = lower_bound(cont + 1, cont + disc_len + 1, raw[i]) - cont; //利用lower_bound找到原数据在cont数组中的地址，减去cont头地址后得到离散结果（即cont中下标）
}

运行结果：

没有重复数据：

大整数离散化 - 示例1
有重复数据：

大整数离散化 - 示例2

二、字符串离散化

【由于暂时没做到相关的题就没做总结2333……

这里就跟字符串哈希的操作是一样的了，
可以查看OI-Wiki上的「字符串哈希」。

其他事项

不去重情况

有时候根据题目要求，相同元素可能会有作用。如下面的问题：

对于数组$a[i]$，问两区间$(l_1,r_1),(l_2,r_2)$间有多少个相同元素。

如要使用较快的：“bitset+取并集”的操作，
这里离散化的时候就不要去重，
并采用以下技巧：

用个$cnt[i]$数组，记录$a_i$在bitset数组$bit[]$出现的次数，
当出现$a_n$时，则使$bit[a_n+cnt[a_n]]++$。

这样，出现了几个$a_n$，就会在$bit[]$中存几个，
取交集的时候就能直接得到个数了。

不去重的原因，是使得相邻两元素离散后的值有差距，
其差距就是该数出现的次数【见上方「本身很大情况」中举的例子】

而去重后，两值间则不会有差距，
无法通过这种方法来存储所有出现的$a_n$。