离散化

离散化有很大的局限性（目前以个人认知来说），几乎只适合在树状数组求逆序对使用。

离散化概念

离散化：把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。
通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。

离散化实现

建立一个结构体包含 v a l val val和 i d id id， v a l val val就是输入的数， i d id id表示输入的顺序。然后按照 v a l val val从小到大排序，如果 v a l val val相等，那么就按照 i d id id从小到大排序。

如果不明白我们可以举了个例子：

总结一下：把原序列中每个元素的值和下标存到结构体内，之后把数组按元素值从小到大排序，数值相同 i d id id小的在前，这样得到的结点的下标值即是离散化结果，等同于原序列的数值。

//val数值    id下标   n 原数组大小
struct node{
	int val, id;
	bool operator < (const node & rhs) const{
		return (this->val < rhs.val) || (this->val == rhs.val && this->id < rhs.id);
	}
}arr[MAXN];

for(int i = 1; i <= n; i++){
	cin >> arr[i].val;
	arr[i].id = i;
}
sort(arr+1,arr+1+n);
for(int i = 1; i <= n; i++){
	cout << arr[i].id << " ";
}