离散化

离散化本质上可以看成是一种 [哈希]，其保证数据在哈希以后仍然保持原来的全/偏序关系。

离散化就是只关心数据的大小之间的关系时候使用的

将其映射成正整数

一般使用情况为数据很大，有负数，有小数

一些算法无法正常运行的时候，就可以用离散化

离散化可以用STL直接完成

十分便捷：

数组下标为0时候的离散化

int C[MAXN];
memcpy(C, A, sizeof(A));
sort(C, C + n);
int l = unique(C, C + n) - C; // l为不重复元素的数量
int L[MAXN];
for (int i = 0; i < n; ++i)
    L[i] = lower_bound(C, C + l, A[i]) - C + 1; // 二分查找

因此已经结束了

数组下标为1的离散化

// a[i] 为初始数组,下标范围为 [1, n]
// len 为离散化后数组的有效长度
std::sort(a + 1, a + 1 + n);
len = std::unique(a + 1, a + n + 1) - a -1;  // 离散化整个数组的同时求出离散化后本质不同数的个数。
for (int i = 1; i <= n; ++i)
L[i]=std::lower_bound(a + 1, a + len + 1, x) - a;  // 查询 x 离散化后对应的编号

如果是vector也是可以直接进行离散化

// std::vector<int> a, b; // b 是 a 的一个副本
std::sort(a.begin(), a.end());
a.erase(std::unique(a.begin(), a.end()), a.end());
for (int i = 0; i < n; ++i)
  b[i] = std::lower_bound(a.begin(), a.end(), b[i]) - a.begin();