离散化

当输入数据跨度大，但是比较稀疏时，就没有必要开几万几百万的数组，可以用离散化求得其相对位置，以节省资源，提高效率。

 1 #include <cstdio>
 2 #include <algorithm>
 3 
 4 using namespace std;
 5 
 6 int n, a[maxn], mp[maxn];
 7 
 8 inline void discretize() {
 9     for (int i = 1; i <= n; ++i)
10         mp[i] = a[i]; //先将原序列复制到mp数组
11     sort(mp + 1, mp + n + 1);
12     mp[0] = unique(mp + 1, mp + n + 1) - mp - 1;
13     //对mp数组排序并去重
14     for (int i = 1; i <= n; ++i)
15         a[i] = lower_bound(mp + 1, mp + mp[0] + 1, a[i]) - mp;
16         //将a数组更新成初始元素的相对大小
17 }