OI|离散化离散化|离散化|离散化模板|#

概念离散化（Discretization），把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。例如：

原数据：1, 999, 100000, 15；处理后：1,3,4,2。
原数据：{100, 200}，{20, 50000}，{1, 400}；处理后：{3,4}，{2,6}，{1,5}。

有的时候，我们会发现对于一个序列，它的值域很大，对应算法的复杂度是 Θ(值域) 的。离散化是程序设计中一个常用的技巧，它可以有效的降低时间复杂度。其基本思想就是在众多可能的情况中，只考虑需要用的值。离散化可以改进一个低效的算法，甚至实现根本不可能实现的算法。例如，在建造线段树空间不够的情况下，可以考虑离散化。
离散化的原理和实现都很简单。为了确保不出错且尽可能地提高效率，我们希望离散化能实现以下几种功能：
1、保证离散化后的数据非负且尽可能的小
2、离散化后各数据项之间的大小关系不变，原本相等的也要保持相等。
由此，找出数据项在原序列中从小到大排第几就是离散化的关键。可以通过下面的方法以 O(n logn) 的时间复杂度完成离散化，n 为序列长度。
离散化一共有两种方法，方法一重复元素离散化后的数字相同，方法二重复元素离散化后的数字不相同。用的最多的是方法一。
方法一：重复元素离散化后的数字相同例如：对于序列 [105，35，35，79，-7]，排序并去重后变为 [-7，35，79，105]，由此就得到了对应关系 -7->1, 35->2, 79->3, 105->4。
基本的步骤可以分为：
1、用一个辅助的数组把你要离散的所有数据存下来。
2、排序，排序是为了后面的二分。
3、去重，因为我们要保证相同的元素离散化后数字相同。
4、索引，再用二分把离散化后的数字放回原数组。
对应的代码如下：

#include // 头文件 const int MAXN = 1e6+4; //n 原数组大小 num 原数组中的元素 lsh 离散化的数组 cnt 离散化后的数组大小 int lsh[MAXN], cnt, num[MAXN], n; for (int i=1; i<=n; i++) { scanf("%d",&num[i]); lsh[i] = num[i]; }sort(lsh+1 , lsh+n+1); //排序 cnt = unique(lsh+1, lsh+n+1) - lsh - 1; //去重//二分查找 for(int i=1; i<=n; i++) { num[i] = lower_bound(lsh+1 , lsh+cnt+1 , num[i]) - lsh; }

在这段代码中，num[] 经过离散，范围就变成了 m。
数据解析比如，这组数据：

1,23424,242,65466,242,0

排序后得到：

0,1,242,242,23424,65466

然后会去重，得到：

0,1,242,23424,65466

然后离散化的到：

1,3,2,4,2,0

注意事项 1、去重并不是把数组中的元素删去，而是重复的部分元素在数组末尾，去重之后数组的大小要减一。
2、二分的时候，注意二分的区间范围，一定是离散化后的区间。
3、如果需要多个数组同时离散化，那就把这些数组中的数都用数组存下来。
方法二：重复元素离散化后的数字不相同例如：对于序列 [105，35，35，79，-7]，排序后变为 [-7，35，35，79，105]，由此就得到了对应关系 -7->1，35->2，35->3，79->4，105->5。
基本的步骤可以分为：
1、用一个辅助的数组把你要离散的所有数据存下来。
2、排序。
3、枚举着放回原数组。
对应的代码如下：

#includestruct Node { int data , id; bool operator < (const Node &a) const { return data < a.data; } }; const int MAXN = 1e5+4; Node num[MAXN]; //原数组 int rank[MAXN]; //离散化后数组 int n; for (int i=1; i<=n; i++) { scanf("%d",&num[i].data); num[i].id = i; }sort(num+1 , num+n+1); for (int i=1; i<=n; i++) { rank[num[i].id] = i; }

这种方法复杂度比上面那一种要优，但不能处理重复元素。它直接用结构体存储原本的数列的元素的位置，然后排序以后将他们再重新赋值。那么 rank[] 就是结构体 num[] 离散化后的结果。
数据解析原始数据：

data: 3 6 5 10 8 id : 1 2 3 4 5

排序以后：

data: 3 5 6 8 10 id: 1 3 2 5 4

离散化以后：

data: 3 5 6 8 10 id: 1 3 2 5 4 rank: 1 2 3 4 5

再按原来的顺序排列：

data: 3 6 5 10 8 rank: 1 3 2 5 4

习题模板题模板题一，http://47.110.135.197/problem.php?id=5237。
模板题二，http://47.110.135.197/problem.php?id=5238。
其他题目洛谷 P1955，程序自动分析，https://www.luogu.com.cn/problem/P1955。
洛谷 P1667，数列，https://www.luogu.com.cn/problem/P1667。
【OI|离散化】VOJ 1056，图形面积，https://vijos.org/p/1056。