前言

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

正文

离散化的使用在OI中使用十分广泛，主要用于数据的处理，那么他到底是个什么东西呢？

通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小，将无穷大集合中的若干个元素映射为有限集合以便于统计。

假设问题涉及int范围内的n个整数$a_i$ ~ $a_n$,这n个整数可能有重复，去重以后共有m个整数。我们要把每个整数$a_i$用一个1~m之间的整数代替，并且保持大小顺序不变，即如果$a_i$x小于（或等于、大于），那么代替$a_i$的整数也小于（或等于、大于）代替$a_j$的整数。

例如：

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

原数据：{100,200}，{20,50000}，{1,400}；

处理后：{3,4}，{2,6}，{1,5}；

离散化也是各种排序算法的一个应用。

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

Code

void discrete(){// 或用STL中的unique
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++){
        if(i==1||a[i]!=a[i-1]) b[++m]=a[i];
	}
}
int query(int x){//查询x映射为1~m之间那个整数
	return lower_bound(b+1,b+m+1,x)-b;
}

关于lower_bound

查找不小于x的元素中最小的一个，并返回指向该元素的迭代器（可以简单的理解为位置？）

后言

生活中的“离散化”的例子还有很多，比如某一中的班级名单，按照学生的成绩排个序，然后从一号开始标，班级内的序号也就是班级内的排名。这也就避免了成绩的差距过大，比如我友链中那几个强者和我这样的菜鸡。