一，id转换

1，id数组

如果一个数组有n个数，且其中包含了从0到n-1的所有数，则称之为id数组

2，基于id数组的重排双射

每一个id数组，都对应一种双射，把一个泛型数组进行重排。

如{3 0 1 2}，就是一个映射，{a b c d}->{d a b c}，可以理解为依次从一个泛型数组中按照id指引的位置取元素。

对于{8 5 6 7}，它需要基于{1 2 3 0}这个id数组进行重排，才能完成排序。

而对于{1 2 3 0}，它需要基于{3 0 1 2}这个id数组进行重排，才能完成排序。

ACM模板里面的VectorOpt::sortId函数，输入{8 5 6 7}，输出{1 2 3 0}，这个函数的功能就是对于每个泛型数组，求出它需要基于哪个id数组进行重排，才能完成排序。

因为比较函数中采用了id作为第二顺序关键字，所以它一定是稳定排序。

3，逆id数组

基于id数组的重排是双射，所以自然有逆映射，而逆映射一定是基于某个数组的重排，我们把这个数组，称为逆id数组。

神奇的是，任意一个id数组，基于它的逆进行id重排，就能完成排序。

也就是说，id数组S 和 sortId(S) 互为逆，上面的{1 2 3 0}和{3 0 1 2}就是一个例子。

一个id数组的逆，有可能是它自身，

如{1 4 3 2}需要基于{0 3 2 1}进行重排，才能完成排序，而{0 3 2 1}需要基于自身进行重排，才能完成排序，而{1 2 3 4}基于{0 3 2 1}进行重排。就会得到{1 4 3 2}

二，离散化

1，离散化

离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。

通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。例如：

（1）原数据：1,999,100000,15；处理后：1,3,4,2；

（2）原数据：{100,200}，{20,50000}，{1,400}；处理后：{3,4}，{2,6}，{1,5}；

PS：本文默认全部采用升序。

2，单射和双射

离散化其实是个映射，有2种表达方式。

（1）只关心数据的大小顺序，采用单射

离散化：{1,999,100000,15} -> {1,3,4,2}

（2）既关心数据的大小顺序，也关心数值本身，采用双射

离散化：{1,999,100000,15} -> {{1,3,4,2}，{1,15,999,100000}}

逆离散化： {{1,3,4,2}，{1,15,999,100000}} ->{1,999,100000,15}

3，模板代码

ACM模板里面的VectorOpt::sortId2函数，输入{8 5 6 7}，输出{3 0 1 2}，这就是离散化，我的模板是从0开始编号，用起来更方便。

离散化得到的，一定是一个id数组。

而sortId2的实现方式，就是sortId(sortId())，因为，排序后数组，基于原数组离散化得到的id数组进行重排，得到的就是原数组。

4，应用实例

ACM经验大杂烩_csdnacm_csuzhucong的博客-CSDN博客里面也有离散化总结

离散化 in https://blog.csdn.net/nameofcsdn/article/details/125179583

离散化 in https://blog.csdn.net/nameofcsdn/article/details/72467970

离散化 in https://blog.csdn.net/nameofcsdn/article/details/114281344

离散化 in https://blog.csdn.net/nameofcsdn/article/details/115140781

离散化 in https://blog.csdn.net/nameofcsdn/article/details/128788885
离散化 in https://blog.csdn.net/nameofcsdn/article/details/118382256

离散化 in https://blog.csdn.net/nameofcsdn/article/details/52076228

离散化 in https://blog.csdn.net/nameofcsdn/article/details/112343443

离散化 in https://blog.csdn.net/nameofcsdn/article/details/118282360

三，计数转换

计数转换，主要

四，反演