可持久化并(xian)查(duan)集(shu)
2024-08-25 08:56:29
随便地点开了这道可持久化并查集,发现了真相...这和并查集有 PI 关系哦.除了find_father(而且还不能路径压缩),全都是线段树0.0
题目链接: luogu.org
题目没什么描述,就是三个操作:
1. 合并 a b
2. 回到第 k 步操作(三个操作均算操作)
3. 查询 a b 在当前版本的并查集中是否在同一棵树中
那么...
对于操作 1 :我们在线段树中修改节点 fa 的父亲为 fb
对于操作 2 :简单,我们直接把当前版本的根指向第 k 版本的根,一行就解决了(引起可持久化的罪魁祸首解决倒是简单)
对于操作 3 :查询 fa 和 fb 输出就好了(貌似就操作 1 有点不好理解)
对于操作 1 ,模拟如图:
代码如下:
//by Judge
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define ls ch[now][0]
#define rs ch[now][1]
#define mid (l+r>>1)
#define swap(a,b) (a)^=(b)^=(a)^=(b)
using namespace std;
const int M=2e5+;
inline int read(){
int x=,f=; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
int n,m,cnt;
int ed[M<<],f[M<<],ch[M<<][],dep[M<<];
inline void build(int& now,int l,int r){ //建树,叶子节点认 左(右)端点 为父亲
now=++cnt; if(l==r){ f[now]=l; return ; }
build(ls,l,mid), build(rs,mid+,r);
}
void update(int& now,int las,int l,int r,int pos,int fa){ //修改 pos 的父亲为 fa
now=++cnt; if(l==r){ f[now]=fa,dep[now]=dep[las]; return ; }
if(pos<=mid) update(ls,ch[las][],l,mid,pos,fa);
else update(rs,ch[las][],mid+,r,pos,fa);
}
int query(int now,int l,int r,int pos){ //询问在 now 版本中 pos 的节点编号
if(l==r) return now;
if(pos<=mid) return query(ls,l,mid,pos);
else return query(rs,mid+,r,pos);
}
void add(int now,int l,int r,int pos){ //增加 now 版本中 pos 所在叶子节点的深度
if(l==r) { ++dep[now]; return ; }
if(pos<=mid) add(ls,l,mid,pos);
else add(rs,mid+,r,pos);
}
int find(int ed,int x){ //查询祖先
int fa=query(ed,,n,x);
if(x==f[fa]) return fa;
return find(ed,f[fa]);
}
int main(){
n=read(),m=read(),build(ed[],,n);
for(int i=,opt,a,b,f1,f2;i<=m;++i)
switch(opt=read()){
case : //不显然
ed[i]=ed[i-],a=read(),b=read();
f1=find(ed[i],a),f2=find(ed[i],b);
if(f[f1]==f[f2]) break;
if(dep[f1]>dep[f2]) swap(f1,f2);
update(ed[i],ed[i-],,n,f[f1],f[f2]);
if(dep[f1]==dep[f2]) add(ed[i],,n,f[f2]); break; //这里 emmm,看上文
case : //显然
ed[i]=ed[read()]; break;
case : //显然
ed[i]=ed[i-],a=read(),b=read();
f1=find(ed[i],a), f2=find(ed[i],b);
puts(f[f1]==f[f2]?"":""); break;
}
return ;
}
上面代码可能出锅,下面代码应该没毛病...
//by Judge
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define ls ch[now][0]
#define rs ch[now][1]
#define mid (l+r>>1)
#define swap(a,b) (a)^=(b)^=(a)^=(b)
using namespace std;
const int M=2e5+;
inline int read(){
int x=,f=; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
int n,m,cnt;
int ed[M<<],f[M<<],ch[M<<][],dep[M<<];
inline void build(int& now,int l,int r){
now=++cnt; if(l==r){ f[now]=l; return ; }
build(ls,l,mid), build(rs,mid+,r);
}
void update(int& now,int las,int l,int r,int pos,int fa){
now=++cnt; if(l==r){ f[now]=fa,dep[now]=dep[las]; return ; }
ls=ch[las][], rs=ch[las][];
if(pos<=mid) update(ls,ch[las][],l,mid,pos,fa);
else update(rs,ch[las][],mid+,r,pos,fa);
}
int query(int now,int l,int r,int pos){
if(l==r) return now;
if(pos<=mid) return query(ls,l,mid,pos);
else return query(rs,mid+,r,pos);
}
void add(int now,int l,int r,int pos){
if(l==r) { ++dep[now]; return ; }
if(pos<=mid) add(ls,l,mid,pos);
else add(rs,mid+,r,pos);
}
int find(int ed,int x){
int fa=query(ed,,n,x);
if(x==f[fa]) return fa;
return find(ed,f[fa]);
}
int main(){
n=read(),m=read(),build(ed[],,n);
for(int i=,opt,a,b,f1,f2;i<=m;++i)
switch(opt=read()){
case :
ed[i]=ed[i-],a=read(),b=read();
f1=find(ed[i],a),f2=find(ed[i],b);
if(f[f1]==f[f2]) break;
if(dep[f1]>dep[f2]) swap(f1,f2);
update(ed[i],ed[i-],,n,f[f1],f[f2]);
if(dep[f1]==dep[f2]) add(ed[i],,n,f[f2]); break;
case : ed[i]=ed[read()]; break;
case :
ed[i]=ed[i-],a=read(),b=read();
f1=find(ed[i],a), f2=find(ed[i],b);
puts(f[f1]==f[f2]?"":""); break;
}
return ;
}
by Judge
最新文章
- opnet学习过程
- unbuntu server (linux系统)下面安装 lamp
- ios之申请后台延时执行和做一个假后台的方法(系统进入长时间后台后,再进入前台部分功能不能实现)
- codevs 3008 加工生产调度[贪心]
- (jdbc)取得数据库自动生成的主键方法
- Linux命令(19)用户权限管理:chown
- eclipse对项目整理分类
- java.lang.NoClassDefFoundError的原因及解决
- ASP.NET中的Request和Respone对象的使用
- SqlDataReader的关闭问题
- leetcode算法: Find Bottom Left Tree Value
- TensorFlow卷积网络常用函数参数详细总结
- JAVA中执行JavaScript代码并获取返回值
- Python的GUI用法1
- python购物车作业
- 定制化rpm包及本地yum仓库搭建
- TF之RNN:TF的RNN中的常用的两种定义scope的方式get_variable和Variable—Jason niu
- mac CodeIgniter和EasyWeChat 开发微信公众号
- 使用ipns 为ipfs 系统自定义域名
- iOS 输入框限制输入字节数