离散化

离散化是一种数据处理的技巧，本质上可以看成是一种 哈希，其保证数据在哈希以后仍然保持原来的全/偏序关系。
https://oi-wiki.org/misc/discrete/
通俗地讲就是当有些数据因为本身很大或者类型不支持，自身无法作为数组的下标来方便地处理，而影响最终结果的只有元素之间的相对大小关系时，我们可以将原来的数据按照排名来处理问题，即离散化。

用来离散化的可以是大整数、浮点数、字符串等等。
最常见方法：排序+去重+二分

//函数接受需要离散化的vector和离散化后对应的数从start开始两个参数
//返回的是离散化的结果vector，下标是离散化追求目标，存的值是原来第i小的数在原数组中排第i个位置
vector<int> discrete(const vector<int>& odata, int start = 0) {
//
    const int n = odata.size();
    auto copy = odata;//对原数组的拷贝操作
    sort(copy.begin(), copy.end());
    // 考虑重复值
     copy.erase(unique(copy.begin(), copy.end()), copy.end());

    vector<int> res(n);
    for (int i = 0; i < n; i += 1) {
        // lower_bound >= 由于数值本身就存在，因此必然是找到=的情况
        res[i] = lower_bound(copy.begin(), copy.end(), odata[i]) - copy.begin() + start;
             
    }
    return res;
}

2.借助 map 自动排序

vector<int> discrete(const vector<int>& odata, int start = 0) {
    const int n = odata.size();
    // C++中的map自带升序效果
    // <数值，下标>
    map<int, int> autoSort;
    for (int i = 0; i < n; i += 1) {
        autoSort[odata[i]] = i;
    }
//autosort排序后，小数在前面，
    vector<int> res(n);
    for (auto it = autoSort.begin(); it != autoSort.end(); ++it) {
        res[it->second] = start;
        start += 1;
    }
    return res;
}
999在原来的数中排名第15小，它会被映射成15，我们需要保证结果和999这个值没有关系，或者只和相对大小的有关。代入题目例子更容易理解，可以看acwing板子题区间和https://www.acwing.com/problem/content/804/