离散化

如果我们遇到一道题，已知里面有很多个可重复的数，不同的数最多有100种，范围在1~10^12不等。我们需要记录每个数出现的次数，但是分配的内存空间不允许我们直接开10^12这么大的数组，所以出现的数本身无法作为下标。这个时候如果题目中数仅相对大小存在意义，我们就可以将它们进行离散化处理之后再用100的数组来储存。

比如数组{3,6,1,9}离散化之后处理为{1,2,0,3}

处理之后范围更小的数常用来做数组下标，在并查集、线段树等情境下也有应用

写的时候突然想到，如果是小数等不允许被用来做下标的元素，条件允许的话也可以用离散化只存储相对大小

流程如下：

通用方法

一、复制数组

首先假设我们拥有一个输入的数组，数组中的数本身不允许我们用来直接做下标。我们先用数组a把他们的值存起来，然后复制一份到数组t。

为方便去重，我们使用从0开始的下标。

作为例子，我们假设数最多有n种，数的范围最大为10^9 ~~（方便写int）~~ ，那么现在我们有：

vector<int> a;

vector<int> t = a;//与a数组内容相同

二、数组排序并去重（视情况）

如果输入的数组中没有重复元素，直接使用sort进行排序即可：

sort(t.begin(),t.end());//默认升序

如果输入的数组中有重复元素，我们就需要先进行排序，再进行复制数组中的去重。

不去重会导致离散化编号之间存在空缺，造成浪费。

我们使用unique函数对复制之后的数组t进行去重：

unique用法：unique(t.begin(), t.end())，返回去重后数组的尾地址的后一格。unique在被使用后会将不重复元素依次移到前面，因此不会打乱原来的排序。同时，后面的不需要的重复元素需要用erase清除。

sort(t.begin(),t.end());//先进行升序排序

t.erase(unique(t.begin(),t.end()),t.end());//先执行unique再执行erase

三、离散化处理进入新数组

t数组已经排序并且没有重复元素，此时t数组的下标的相对大小与元素的相对大小一样，并且下标数据小没有空间浪费，我们就可以让t数组的下标成为对应元素的离散化编号。

问题来了，我们发现t数组中的元素的顺序和a数组不一样了，同时重复的元素也没有了，很显然无法直接作为处理后的a数组来进行使用。那我们应该怎么把原数组a中的元素用他们相应的离散化编号来替代并存入新的数组呢？

（这里可以将离散化编号直接塞回原数组a）

四、lower_bound二分查找的办法（通用）

原理是按照a数组的下标从小到大去看，去找a数组数据在t中的位置，将t对应的位置下标存入新数组的a数组对应的下标中。我们之前已经知道了，t数组中数据的位置就是他们的离散化编号。

流程大概是这样的：

a[x] -> lower_bound发现t[y] = a[x] -> result[x] = y

有代码：

vector<int> result(n);

for(int i = 0; i < n; i++ )
{
  result[i] = lower_bound(t.begin(),t.end(),a[i]) - t.begin();
}

补充方法：用pair事先保存原下标（不需要t数组，简单版本无法处理元素重复的情况）

我们直接从一开始的a数组开始处理即可。这种方法不用普通的t数组，而是使用pair数组作为辅助数组。

这种方法的思路是在存储原值的同时，也保存这个值在原数组中的下标。这样可以替代方法一中搜索的过程。这种方法因为省去了二分查找的过程直接写回所以速度较快，但是下面给出的是简单版本，不能直接处理重复元素。此处我们使用pair存储之后会直接排序，把顺序当做离散化编号，不会去重。

有重复元素的话，遍历values遇到重复元素就特殊处理一下（如果当前元素的first和前一个元素相同，就让它继续使用前一个元素的离散化编号；如果不同，编号才加一。）的写法也可以。

这种方法需要建一个新的pair数组values，根据原数组a来存储原值和原下标。

vector<pair<int,int>> values;

for(int i = 0; i < n; i++ )
{
  values.push_back({a[i] , i});
}

我们依据values存储的原下标和原值的对应关系来进行操作。流程：

values按照first排序 -> y是离散化编号 -> values[y].second是该元素的原下标 -> result[values[y].second] = y

sort(values.begin(),values.end());//pair数组默认按pair的前值升序排序

for(int i = 0; i < n; i++ )
{
  result[values[i].second] = i;//将序号，即离散化编号赋值给结果数组原下标的位置，使离散化编号i替代相应的原值
}

自此，离散化完成。我们从原数组a得到了新的结果数组result，现在我们可以使用result数组中的较小的元素在我们需要的地方作为下标了。