关于一个蒟蒻的成长历程
老师：”今天学习并查集……（略）”
老师：”好了讲完了，做几个题练练手吧。”
” woc ，我 TM10 分。算了算了，先做下一题吧。”
——2021.05.26
“写挂的题快消完了，还差最后一个。”
” cao ，还是 10 分。”
——2021.09.30
“最后一个题，我今天必须 A 了。”
——2021.10.17 20:05 pm
“woc 50 了，加油加油！”
——2021.10.17 20:16 pm
“九点打不过去就看题解，就看一眼。”
——2021.10.17 20:28 pm
“我放弃……太难了。”
——2021.10.17 21.02 pm
” cao ，离散化，不会，怪不得。正好学学离散化吧。”
——2021.10.17 21.02 pm
附图：
果然我还是太蒻了。。。。。
为了纪念本蒟蒻学习了离散化，特写此文章纪念一下。
此题思路：
对于结构体 ({i,j,e}) ，按照 e sort 一下，先将所有 (e=1) 的两点放到一个并查集里，然后再对 (e=0) 的两点进行找根，若根相同，说明两点应该是相同的，矛盾，输出 “NO” ；若所有的都不矛盾，则输出 “YES” 。
这样就可以得到 50 分的好成绩。
那此题为什么要用离散化呢？
对于两个点合并的时候， (i,j\in[1,10^9])，那么 fa 就要开到 1e9，显然，数组开不了这么大。
这时就要离散化了。
离散化，就是把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。
——百度百科。
没看懂
举个例子，我们要找序列中最小元素的下标，如 1314,114514,521,2147483647，那么这个序列就等价于 2,3,1,4，最小元素的下标就是 3 。
那么，如何离散化呢？
为方便表示，我们用 a 表示离散化之前的数组， b 表示离散化之后的数组。
用一个结构体来储存原数组以及所对应的下标。
先按照 val 将数组排序，然后就能得到他们的相对的位置关系。
然后按顺序访问 a 的下标，并依次写到 b 中。
代码：
const int inf=1e5+7;
int n,b[inf];
struct data{
int val,id;
}a[inf];
bool cmp(data x,data y){return x.val
时间复杂度为 (O(n\log n))，瓶颈在排序。
这种方法是不能去重的（至少我不会），想去重的话建议用方法二。
C++自带 STL。
一个去重函数： unique(start,end+1)，范围是 (\left[start,end\right))。
一个二分查找函数： lower_bound(start,end+1,key)，范围是 (\left[start,end\right))。
先拷贝原数组，再 sort，再 unique，最后 lower_bound，然后你就成功将数组离散化了。
其实就是利用 lower_bound 找到原数组在排序后的数组中的位置。
Code:
#include
#include
using namespace std;
const int inf=1e5+7;
int n,num;
int a[inf],b[inf],bok[inf];
int main()
{
scanf("%d",&n);
for(int i=1;i
离散化之后，数据变小了，这个题再用之前 50 分 的思路打就能切掉了。
Code:
const int inf=1e6+7;
int qwq,n;
int op[inf],fa[inf];
struct data{
int u,v,op;
bool operator b.op;
}
}a[inf];
int find(int x)
{
if(fa[x]==x)return fa[x];
return fa[x]=find(fa[x]);
}
int bok[inf],num;
int main()
{
qwq=re();
while(qwq--)
{
n=re();num=0;
for(int i=1;i
随着学习的深入，会发现离散化的用处非常广。其中最重要的用处在和桶相关的一些算法上（如权值线段树、主席树、某些分块、莫队）。
比如：
Original: https://www.cnblogs.com/Zvelig1205/p/16140686.html
Author: Zvelig1205
Title: 离散化
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/604943/
转载文章受原作者版权保护。转载请注明原作者出处！