离散化
离散化的概念¶
首先，什么是离散化？
离散化就是比相对大小。
通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。
原数：131021 546412 973324
离散化后数据：1 2 3
离散化的用途¶
当有些数据本身很大， 自身无法作为数组的下标保存对应的属性。如果这时只是需要这堆数据的相对属性， 那么可以对其进行离散化处理（当然也可以哈希）。当数据只与它们之间的相对大小有关，而与具体是多少无关时，可以进行离散化。
（这样就可以开桶了）
离散化的写法¶
我们只需要维护两个事情不变：
-
保证离散化之后的数据尽可能地小而且非负。
-
离散后的数据要保持原本的大小关系，原本相等的也要保持相等，否则就是错误的离散。（一对一的双射）
找出原数据在序列中的序位就是离散化的关键。
STL-vector 实现：¶
int a[maxn];
vector<int> b;
for(int i=1;i<=n;i++) {
scanf("%d",&a[i]);
b.push_back(a[i]);
}
sort(b.begin(),b.end(),cmp); // 不是结构体，不用写cmp
b.erase(unique(b.begin(),b.end()),b.end()); // 直接删掉，不用维护size
for(int i=1;i<=n;i++)
a[i]=lower_bound(b.begin(),b.end(),a[i])-b.begin();
//算出在a[i]在b中的下标 并覆盖
解释：
unique去重，返回无重复序列的尾迭代器
lower_bound返回第一个大于等于val的迭代器（upper是大于）
输入a[i]之后紧接着保存同样的b[i]作为副本。然后对副本b进行去重，并保存b数组去重后的长度（size）。
然后开始离散化，直接把对应元素转换成相应的数组下标即可。
源数据和离散数字相互转化¶
对于离散后的数字找原数字，只需要访问离散化的\(b[i]\)存储
原数字找离散数字，则需要利用 lower_bound() 找出在离散化的\(b[i]\)的位置