C++ 离散化：unique 减 1 和 lower_bound 不减 1 的原因

在 C++ 中，离散化是一种将数据映射到较小范围内的常见技巧，通常使用 unique 和 lower_bound 函数实现。本文将解释在离散化中，为什么 unique 函数需要减 1 来获取去重后的个数，而 lower_bound 函数则不需要减 1。

unique 函数的返回值

unique 函数返回的是去重后的范围的尾部的迭代器，而不是去重后的个数。因此，在计算去重后的个数时，需要用 unique 函数返回的迭代器减去数组的起始地址 b，并再减去 1。例如，以下代码展示了如何使用 unique 函数去重并获取去重后的个数：

int e = unique(b+1, b+1+n)-b-1; // 去重并得到去重后的个数

lower_bound 函数的返回值

lower_bound 函数返回的是在指定范围内第一个不小于给定值的元素的迭代器，因此不需要减 1。lower_bound 函数返回的迭代器指向的位置，即是原数组中第一个不小于给定值的元素的下标。例如，以下代码展示了如何使用 lower_bound 函数将原数组 a 中的元素映射到去重后的数组 b 中的下标位置：

for(int i = 1; i < n+1; i++) a[i] = lower_bound(b+1, b+1+e, a[i])-b;

总结

在离散化中，通过 unique 函数去重后，得到的数组 b 中的元素个数是 e，通过 lower_bound 函数将原数组 a 中的元素映射到去重后的数组 b 中的下标位置。