// 存储所有待离散化的值，alls中存储的是下标
vector<int> alls; 
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素

数组下标对应映射关系，当需要对离散化后的数组进行操作时，对原数组的数组下标也需要进行离散化
离散化后的新值需要再开一个数组a[]来存储, 查询原数组区间和时可使用新数组a[]的前缀和数组s[]

// 二分求出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
}

STL函数实现查询

void query( int x )
{
    return lower_bound(b+1, b+m+1, x ) - b; // b为离散化后的数组

}