离散化相关问题
分析
离散化并不是解题方法 它是某些数据范围过大的题所必要的手段
若题目给的范围为无穷大 或者\(10^9\)这类的东西
我们是无法用数组进行表示出来的
既然无法表示出来 更别说后续的解题了
那么我们就需要对原数据区进行一些离散化的操作
把一些不需要的元素（0） 去除掉
只留下一些有意义的值 组成一个新的区间 这个区间可以被我们用数组表示出来
这个过程也叫做映射
要实现这种大到小的映射 方法不唯一
你可以像模板那样手写离散化
手写离散化 本质是把下标做值 存在从0开始的数组里 这样就可以得到一个新的下标 为了使这些下标唯一映射 我们要进行 排序去重 然后核心就在于find 这个find使得我们真实下标和映射下标得到了对应 只有对应了 我们的离散化才具有意义 用法大概是 找原区间里某个数的映射出的新下标 在这个新下标处干一些事情 把每一步的意义记清楚 不然容易晕头转向的
当然 也可以不手写离散化 直接用map实现离散化
因为map是用键值对存储 我们完全可以把 有意义的下标 做为键 把要操作的值 作为值
这就相当于 我们原本的两个数组（映射数组、操作数组）被合并成了一个map 并使用键值进行关联 我们遍历map就相当于遍历出了所有有意义的下标（m.first) 用于操作的数就在m.second
当然还有用哈希函数 哈希表等等方法实现离散化
手写不过是方法之一 离散化本质也就只是一个手段
不过不得不提的是 手写离散化确实时间效率高很多
想这类题的话 一开始也不是直接从离散化入手
应该先想在数组中我该做哪些操作 然后发现数组存不下或者太多没意义的值 才去做一下离散化
然后写的时候 就先写离散化 再用离散化后的下标做操作
感觉基本要和差分前缀和碰在一起 （可能因为差分 0不影响答案 离散化也有这个特性）
💬 评论