离散化

通过哈希表进行离散化

原理

  建立一个哈希表，通过每次将新的值映射为一个递增的n来达到离散化的目的。这种离散化不要求顺序，只需要值的对应即可。

模板

int find(int x)
{
    if (S.count(x) == 0) S[x] = ++ n;
    return S[x];
}

排序+去重+二分查找进行离散化

原理

  当要求有序的离散化时，需要将需要离散化的坐标排序，之后去重，最后使用二分查找获得映射后的坐标。这里其实相当于将排序后的数组下标作为离散化后的值。这种离散化的好处就是保序，当计算原下标3-7之间的结果时，直接计算离散化之后find(3)-find(7) = 3 - 5之间的结果即可。

模板

//通过find函数找到原值的对应下标，即离散化之后的值
int find(int x)
{
    int l = 0, r = n - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (a[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r;
}
//排序+去重
sort(pts.begin(), pts.end());
pts.erase(unique(pts.begin(), pts.end()), pts.end());

例题

AW.802 区间和（简单）