离散化特指整数的离散化, 且是有序的离散化

离散化的含义: 有一些数, 值域比较大$[0,10^9]$ , 数量不多,大概是$10^5$个

有些题目, 我们可能需要以这些值为下标, 但是我们又不想开一个长度为$10^9$的数组, 所以我们需要一种方式把这$10^5$个数映射到连续的数$[0,n-1]$上

离散化: 对于数组 a, 有 $1 ,3,100,2000,10000$ 这五个数, 我们把他映射到从 0 开始的自然数$[0,1,2,3,4]$, 这个过程就叫做离散化

可能遇到的问题:

1. a 中可能有重复元素 —–> 需要去重
2. 如何快速算出任意值 $x$ 离散化后的值 —-> 利用数组有序,然后二分求下标

离散化比较明显的好处就是节省空间

为这组数组建立离散化对应的下标: list+二分

1. 现将所有的数存到 list 中, 去重, 排序.

2. 二分拿到数在 list 中的下标

这样, 就能完成离散化的下标映射, 接下来就是利用这个新下标来做别的事情, 比如求区间和之类的

题目:

区间和

格子染色