定义

在不改变数据相对大小的条件下，对数据进行相应的缩小。

人话：面对数据比较大的情况(比如让你开 1e9 的数组)，会 mle，所以引入离散化，将大数据映射到一个较小的值域来处理。

实现

STL

• 排序 sort
• 去重 unique
• 二分索引 lower_bound

// 假定对一个数组去重
int res = unique(a+1, a+1+n) - (a+1);
// 函数返回去重之后的尾迭代器，即去重之后末尾元素的下一个位置。

这里相当于将原来的每个数映射为排序去重之后的数组中相同元素的下标，此时映射之后的数的相对大小关系不变

#include <bits/stdc++.h>
using namespace sts;
int n,res,tot,a[MAXN],b[MAXN];
int main() {
	scanf("%d",&n);
	for(register int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
		b[++tot]=a[i]; //b[]是a[]的副本
	}
	sort(b+1,b+1+tot);  //第一步：排序
	res=unique(b+1,b+1+tot)-(b+1);  //unique函数计算出去重后的元素个数，存在res中
	for(register int i=1;i<=n;i++) {
		a[i]=lower_bound(b+1,b+1+res,a[i])-b;  //lower_bound函数进行索引
	}
	return 0;
}