离散化用途

数组范围很大,但是数组中用到的数却不是很多的情况

离散化步骤

1. 排序 ---- 便于处理
2. 去重 ---- 可能有重复元素
3. 二分 ---- 查找离散化后在新数组中的下标

离散化模板

vector<int> alls; // 存储离散化后的值
sort(alls.begin(),alls.end()); //排序
//unique () return An iterator to the element that follows the last element not removed.
alls.erase(unique(alls.begin(), alls.end()), alls,end()); //去重

//二分求出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; //映射到1,2,...,n
}

unique()函数可以自己实现：

写法1

vector<int>::iterator unique(vector<int> &a)
{
    int j=0;
    for(int i=0;i<a.size();i++)
        if(!i || a[i] != a[i-1])
            a[j++] = a[i];
    //a[0]~a[j-1]所有a中不重复的数
    return a.begin()+j;
}

写法2

vector<int>::iterator unique(vector<int> & a){
    int j = 0;
    for(int i = 0; i < a.size(); i ++){
        if(a[i] != a[i + 1]) a[j ++] = a[i];
    }
    return a.begin() + j;
}

经典案例

区间和

refenrence