离散化
离散化
关于一个蒟蒻的成长历程
老师：“今天学习并查集……（略）”
老师：“好了讲完了，做几个题练练手吧。”
比如： P1955
“ 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 。
那么，如何离散化呢？
方法一
为方便表示，我们用 sta 表示离散化之前的数组，end_ 表示离散化之后的数组。
用一个结构体来储存原数组以及所对应的下标。
先按照 val 将数组排序，然后就能得到他们的相对的位置关系。
然后按顺序访问 sta 的下标，并依次写到 end_ 中。
代码：
#include
#include
using namespace std;
const int inf=1e5+7;
int n,end_[inf];
struct data{
int val, id;
}sta[inf];
bool cmp(data a,data b){return a.val 这种方法是不能去重的（至少我不会），想去重的话建议用方法二。
方法二
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 sta[inf],end_[inf],cpy[inf];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&sta[i]),cpy[i]=sta[i];
sort(sta+1,sta+n+1);
num=unique(sta+1,sta+n+1)-(sta+1);
for(int i=1;i<=n;i++)
end_[i]=lower_bound(sta+1,sta+num+1,cpy[i])-sta;
for(int i=1;i<=n;i++)
printf("%d ",end_[i]);
return 0;
}
离散化之后，数据变小了，这个题再用之前 50 分 的思路打就能切掉了。
Code:
#include
#include
#include
using namespace std;
inline int re()
{
int s=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
s=s*10+ch-48,ch=getchar();
return s*f;
}
inline void write(int s)
{
if(s<0)s=-s,putchar('-');
if(s>9)write(s/10);
putchar(s%10+48);
}
inline void wr(int s){write(s),putchar('\n');}
const int inf=1e7+7;
int QWQ,n;
int op[inf],fa[inf];
struct data{
int u,v,op;
}a[inf];
bool cmp(data a,data b)
{
return a.op>b.op;
}
int find(int x)
{
if(fa[x]==x)return fa[x];
return fa[x]=find(fa[x]);
}
int disc_[inf],cnt;
int main()
{
QWQ=re();
while(QWQ--)
{
memset(disc_,0,sizeof(disc_));
memset(a,0,sizeof(a));
memset(fa,0,sizeof(fa));
bool bol=1;int num=0;
n=re();
for(int i=1;i<=n;i++)
{
a[i].u=re();a[i].v=re();a[i].op=re();
disc_[++num]=a[i].u;disc_[++num]=a[i].v;
}
sort(disc_+1,disc_+num+1);
num=unique(disc_+1,disc_+num+1)-disc_;
for(int i=1;i<=n;i++)
{
a[i].u=lower_bound(disc_+1,disc_+num+1,a[i].u)-disc_;
a[i].v=lower_bound(disc_+1,disc_+num+1,a[i].v)-disc_;
}
for(int i=1;i<=num;i++)fa[i]=i;
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)
{
if(a[i].op){
int r1=find(a[i].u),r2=find(a[i].v);
if(r1!=r2)fa[r1]=r2;
}
else
{
int r1=find(a[i].u),
r2=find(a[i].v);
if(r1==r2)
{
puts("NO");bol=0;
break;
}
}
}
if(bol)puts("YES");
}
return 0;
}
后记
随着学习的深入，会发现离散化的用处非常广。其中最重要的用处在于权值线段树和主席树。
比如：
P5490
离散化 +
P3834
离散化 +
P4197
+ 离散化的主席树