离散化

给出一列数字，很多时候，这些数真实值不重要，而相对大小关系很重要。“离散化”就是用数字的相对值代替绝对值，缩小值域范围。

可以对利用一个辅助数组 $b[]$ ,初值为原数组，进行排序，排序后，再$b$数组中进行二分查找 $a_i$ ,在 $b$ 数组中所处的位置就是 $a_i$ 的相对大小。

核心代码：

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

例题 B3694 数列离散化

大多数离散化不需要去重，只要能表示出相对大小关系就可以，但本题需要进行去重处理，可以使用 unique(b+1,b+n+1) 去重，此函数返回去重后最后一个数下一个位置（迭代器或指针）, int m=unique(b+1,b+n+1)-b-1 可以获得去重后数组元素个数。

参考代码：点击