离散化模板

假设需要存储一些键值对，它们的 key 分别为{1, 8, -10, 499, 231, 76, 21747483647}——一组无序且边界极大的数

直接存数组是不行的 arr[21747483647]、arr[-10] 都不合理

如果直接使用 map 去存，每次插入都是一次树型的调整，虽然大致是 nlogn，但是肯定要大一点的。对于只在初始化阶段建表，后期不再改动的情况，是挺浪费的

这个时候使用离散化是更好的方法

// 把 pairs 按照 key 递增顺序排序，cmp 自己实现
sort(pairs, pairs + n, cmp);

for (int i = 0; i < n; i++){
  v[i] = pairs[i].value;
}

for (int i = 0; i < n; i++){
  k[i] = pairs[i].key;
}
1
2
3
4
5
6
7
8
9
10

使用时很方便，比如要找 key=499 对应的数据，只需要

v[lower_bound(k, k + n, 499) - k];
1

可以 define 一个宏，用起来方便

#define KLOC(X) (lower_bound(k, k + n, (X)) - k)
1

lower_bound()是纯二分，logn，所以说这个也是 nlogn，比 map 快的 nlogn

vector 版本：

sort(pairs.begin(), pairs.end(), cmp);
...
v[lower_bound(k.begin(), k.end(), 499) - a.begin()];
1
2
3