标签：下标 val int 简介 离散 哈希 data
简介(Introduction)
离散化 —— 把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率，即：在不改变数据相对大小的条件下，对数据进行相应的缩小。
离散化本质上可以看成是一种
哈希，其保证数据在哈希以后仍然保持原来的 全/偏序 关系。
描述(Description)
- 离散化用于处理一些个数不多，但是数据本身很大但是仍需要作为数组等无法过大的下标时，我们可以处理一下这些大的下标，并且依然保持其原序。
- 通俗地讲就是当有些数据因为本身很大或者类型不支持，自身无法作为数组的下标来方便地处理，而影响最终结果的只有元素之间的相对大小关系时，我们可以将原来的数据按照从大到小编号来处理问题
模板代码(Template Code)
#include <bits/stdc++.h>
using namespace std;
const int N=500010; //Customize a range
struct data{
int id;//key
int val;//value
}olda[N];//Raw data before discretization
int newa[N];//Discretized results
bool cmp(data x,data y)
{
return x.val<y.val;
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i+
标签：下标,
val,
int,
简介,
离散,
哈希,
data
From： https://blog.csdn.net/Qpeterqiufengyi/article/details/137181177