离散化详解是什么意思？

离散化 两种 第二种不理解，实际没什么用 第一种： 离散化是由于数据个数少而数据最大值很大时要将数据直接作为数组下标时空间过大时而为了减小空间占用又不破坏数据关系的一种方法 离散化本质上可以看成是一种 哈希 只不过哈希函数是二分查找变量编号所在下标罢了 哈希值就是变量对应的数组下标 不存在冲突，是完美哈希 来自 https://oi-wiki.org/misc/discrete/ 我们把变量本身排序并去重（避免相同元素离散化后不同），然后在把变量作为数组下标时用二分查找（lower_bound)找到变量所在数组的下标，把这个下标作为我们想要的数组下标 这样这个下标最大值只是与数据个数有关 为什么离散化可以保证数据关系呢? 因为当把变量排序去重后，每个变量编号都有唯一的数组下标（不重复） 每个数组下标都有唯一的变量编号 因此我们完全可以用数组下标代替变量编号，只需要二分就可以利用编号求出数组下标，而这样最大只有数据个数个，空间减小了 如noi2015程序自动分析 P1955 [NOI2015] 程序自动分析 https://www.luogu.com.cn/problem/P1955 并查集基本应用 为什么可以用并查集？ 因为相等具有传递性 x1=x2 x2=x3 则 x1=x3 所以对于相等条件可以用并查集合并，然后用不等条件去判断 不等会不会自相矛盾？ 这就是在讨论不等号的传递性 即这题为什么不能用加权或种类并查集 若x1!=x2 x2!=x3 则既不能推出x1=x3,也不能推出x1!=x3 不等号本身不具有任何传递性 1!=2 2!=3 此时1!=3 1!=2 2!=1 此时1=1 因此不能用不等号来判断相等的错误 由于不等号不具有传递性 所以无论怎么不等都不会矛盾 那么这个题不能在线做，不能根据不等判断相等，而要离线 先把所有相等关系先提出来合并，然后用相等来判断不等 对于每个不等式，若两个变量在一个并查集中即相等则矛盾，若不在，则不矛盾 问题是\(n\)不大，当\(i，j\)太大了，\(1e9\) 开不下，可以用map和unordered_map，但是复杂度大 更好用离散化和哈希 哈希就是和不重复数字差不多 把fa数组开哈希和结构体 然后每一个哈希值下挂一个vector 模数\(1e6+1\) 用求余法定址 查找时把\(x\)的哈希值求出 遍历它的vector，找到编号和它相等的，把这个的父亲记录下来，并且开一引用，跳出循环，递归找，把返回值再赋值给引用变量 当然，当父亲等于自身时应该返回自身，说明是根 合并时若\(x\)和\(y\)不在一个并查集就把它们的根随便合并一下 不能用启发式合并，这样要再开一个哈希，太麻烦了 初始化就为空可以，输入时再判断 另外一个问题：无论等于还是不等都要把变量输入时再始化，即若变量下的vector空就push一个，当然不空时只有相等时合并 至于离散化，同样记录下所有变量，从小到大在一个数组中排序去重，然后给定一个变量，就把这个变量在数组中二分查找一下下标，以这个下标作为fa的编号 单次只是\(logn\)的查找 为什么离散化可以呢? 因为当把变量排序去重后，每个变量编号都有唯一的数组下标（不重复） 每个数组下标都有唯一的变量编号 因此我们完全可以用数组下标代替变量编号，只需要二分就可以利用编号求出数组下标，而这样最大只有\(1e5\)个，空间减小了