..
离散化
含义
整数有序离散化:
有一个范围大个数少的数组a，
将其元素映射到从0开始的自然数下标
- 问题1：
a[]中有重复元素->去重 - 问题2：如何算出
a[i]离散化后的序 -> 二分
性质
值域跨度大但非常稀疏。
模版
vector<int> alls;//存储所有待离散化的值
sort(alls.begin(), alls.end());//将所有值排序
alls.erase(unique(alls.begin(),alls.end()), alls.end());//去掉重复元素
unique():将重复元素移至尾部并返回非重部分尾下标
//二分求出x对应的离散化的值
int find(int x) //找到第一个大于等于x的位置
{
int l = 0, r = alls.size() - 1;
while (l < r)
{
int mid = l + r >> 1;
if (alls[mid] >= x) r = mid;
else l = mid + 1;
}
return r + 1;
}