概述

离散化是程序设计中一个常用的技巧，它可以有效的降低时间复杂度。其基本思想就是在众多可能的情况中，只考虑需要用的值。离散化可以改进一个低效的算法，甚至实现根本不可能实现的算法。要掌握这个思想，必须从大量的题目中理解此方法的特点。例如，在建造线段树空间不够的情况下，可以考虑离散化。

数据的离散化

有些数据本身很大， 自身无法作为数组的下标保存对应的属性。如果这时只是需要这堆数据的相对属性， 那么可以对其进行离散化处理。当数据只与它们之间的相对大小有关，而与具体是多少无关时，可以进行离散化。

例如：

91054与52143的逆序对个数相同。

设有4个数：

1234567、123456789、12345678、123456

排序：123456<1234567<12345678<123456789

=>1<2<3<4

那么这4个数可以表示成：2、4、3、1

使用STL算法离散化

思路是：先排序，再删除重复元素，最后就是索引元素离散化后对应的值。

假定待离散化的序列为a[n]，b[n]是序列a[n]的一个副本，则对应以上三步为：

sort(sub_a,sub_a+n);

int size=unique(sub_a,sub_a+n)-sub_a;//size为离散化后元素个数

for(i=0;i<n;i++)

a[i]=lower_bound(sub_a,sub_a+size,a[i])-sub_a + 1;//k为b[i]经离散化后对应的值

对于第3步，若离散化后序列为0,1,2,...,size - 1则用lower_bound，从1,2,3,...,size则用upper_bound。其中lower_bound返回第1个不小于b[i]的值的指针，而upper_bound返回第1个大于b[i]的值的指针，当然在这个题中也可以用lower_bound然后再加1得到与upper_bound相同结果，两者都是针对以排好序列。使用STL离散化大大减少了代码量且结构相当清晰。