acm常用方法——离散化

离散化
什么是离散化？为什么要离散化？竞赛中怎样快速的实现离散化？

什么是离散化？
离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。——百度 通俗地来说 离散化就是将一个不连续区间的值，映射在一个连续的数组当中去。 假如原数组为：{1，1000000000000，30，2} 离散过后数组为：{1，2，3，4}
为什么要离散化？
在acm竞赛中通常会有这种问题: 求一个区间【l,r】的和？ （数据范围通常是1~1e6） 通常的解决方法有两种：
暴力求和。时间超限前缀和求和。数组中含有1e6的时候你将数组开到1e6肯定不现实
这时候就需要将原数组压缩成我们可以接受的小数组，之后进行前缀和求解。 这就是离散化的作用。
竞赛中怎样快速的实现离散化？
这里最简便的方法就是利用STL里边的vector进行离散化操作 只需两步
排序 sort(a.begin()

acm常用方法——离散化最先出现在Python成神之路。