可持久化并查集
Orz hzwer & zyf
呃学习了一下可持久化并查集的姿势……其实并查集就是一个fa数组（可能还要带一个size或rank数组），那么我们对并查集可持久化其实就是实现一个可持久化数组……
那么我们用可持久化线段树实现一下可持久化数组就可以了- -
一开始我比较傻逼，想着：中间的叶子节点不是没用嘛？什么信息也不存……然而如果不这样的话，难道你每次修改，新建N个指针吗？这样可以保证每次只新建O(logn)个节点出来……
（是不是a+b problem也是类似的原因？并不知道诶……去做下看看好了）
嘛那么这里维护一下fa和size就可以了。。。
/**************************************************************
Problem: 3673
User: Tunix
Language: C++
Result: Accepted
Time:64 ms
Memory:7608 kb
****************************************************************/ //BZOJ 3673
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
typedef long long LL;
inline int getint(){
int r=,v=; char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-;
for(; isdigit(ch);ch=getchar()) v=v*-''+ch;
return r*v;
}
const int N=2e4+;
/*******************template********************/ int n,m,cnt,rt[N]; struct node{
int l,r,v,size;
}t[N*];
#define L t[o].l
#define R t[o].r
#define mid (l+r>>1)
#define lch L,l,mid
#define rch R,mid+1,r void build(int &o,int l,int r){
o=++cnt;
if (l==r) {t[o].v=l;t[o].size=;return;}
build(lch);
build(rch);
}
void update(int &o,int l,int r,int pos,int v){
t[++cnt]=t[o], o=cnt;
if (l==r) {t[o].v=v; return;}
if (pos<=mid) update(lch,pos,v);
else update(rch,pos,v);
}
void modify(int &o,int l,int r,int pos,int v){
t[++cnt]=t[o], o=cnt;
if (l==r) {t[o].size+=v; return;}
if (pos<=mid) modify(lch,pos,v);
else modify(rch,pos,v);
}
int queryv(int o,int l,int r,int pos){
if (l==r) return t[o].v;
if (pos<=mid) return queryv(lch,pos);
else return queryv(rch,pos);
}
int querysz(int o,int l,int r,int pos){
if (l==r) return t[o].size;
if (pos<=mid) return querysz(lch,pos);
else return querysz(rch,pos);
}
int getfa(int x,int y){
int now=y,nxt=queryv(rt[x],,n,y);
while(now!=nxt){
now=nxt;
nxt=queryv(rt[x],,n,now);
}
return now;
} int main(){
#ifndef ONLINE_JUDGE
freopen("3673.in","r",stdin);
freopen("3673.out","w",stdout);
#endif
n=getint(); m=getint();
build(rt[],,n);
int cmd,x,y,ans=;
F(i,,m){
rt[i]=rt[i-];
cmd=getint();
if (cmd==){
x=getint(); y=getint();
int f1=getfa(i,x),f2=getfa(i,y),
s1=querysz(rt[i],,n,f1),s2=querysz(rt[i],,n,f2);
if (s1<s2) swap(f1,f2);
modify(rt[i],,n,f1,s2);
update(rt[i],,n,f2,f1);
}else if (cmd==){
rt[i]=rt[getint()];
}else if (cmd==){
x=getint(); y=getint();
int f1=getfa(i,x),f2=getfa(i,y);
printf("%d\n",ans=(f1==f2));
}
}
return ;
}
(3673)
/**************************************************************
Problem: 3674
User: Tunix
Language: C++
Result: Accepted
Time:1336 ms
Memory:158308 kb
****************************************************************/ //BZOJ 3674
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
typedef long long LL;
inline int getint(){
int r=,v=; char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-;
for(; isdigit(ch);ch=getchar()) v=v*-''+ch;
return r*v;
}
const int N=2e5+;
/*******************template********************/ int n,m,cnt,rt[N]; struct node{
int l,r,v,size;
}t[];
#define L t[o].l
#define R t[o].r
#define mid (l+r>>1)
#define lch L,l,mid
#define rch R,mid+1,r void build(int &o,int l,int r){
o=++cnt;
if (l==r) {t[o].v=l;t[o].size=;return;}
build(lch);
build(rch);
}
void update(int &o,int l,int r,int pos,int v){
t[++cnt]=t[o], o=cnt;
if (l==r) {t[o].v=v; return;}
if (pos<=mid) update(lch,pos,v);
else update(rch,pos,v);
}
void modify(int &o,int l,int r,int pos,int v){
t[++cnt]=t[o], o=cnt;
if (l==r) {t[o].size+=v; return;}
if (pos<=mid) modify(lch,pos,v);
else modify(rch,pos,v);
}
int queryv(int o,int l,int r,int pos){
if (l==r) return t[o].v;
if (pos<=mid) return queryv(lch,pos);
else return queryv(rch,pos);
}
int querysz(int o,int l,int r,int pos){
if (l==r) return t[o].size;
if (pos<=mid) return querysz(lch,pos);
else return querysz(rch,pos);
}
int getfa(int x,int y){
int now=y,nxt=queryv(rt[x],,n,y);
while(now!=nxt){
now=nxt;
nxt=queryv(rt[x],,n,now);
}
return now;
} int main(){
#ifndef ONLINE_JUDGE
freopen("3674.in","r",stdin);
freopen("3674.out","w",stdout);
#endif
n=getint(); m=getint();
build(rt[],,n);
int cmd,x,y,ans=;
F(i,,m){
rt[i]=rt[i-];
cmd=getint();
if (cmd==){
x=getint()^ans; y=getint()^ans;
int f1=getfa(i,x),f2=getfa(i,y),
s1=querysz(rt[i],,n,f1),s2=querysz(rt[i],,n,f2);
if (s1<s2) swap(f1,f2);
modify(rt[i],,n,f1,s2);
update(rt[i],,n,f2,f1);
}else if (cmd==){
rt[i]=rt[getint()^ans];
}else if (cmd==){
x=getint()^ans; y=getint()^ans;
int f1=getfa(i,x),f2=getfa(i,y);
printf("%d\n",ans=(f1==f2));
}
}
return ;
}
(3674)
(3674为强制在线，且数据范围20W)
3673: 可持久化并查集 by zky
Time Limit: 5 Sec Memory Limit: 128 MB
Submit: 757 Solved: 319
[Submit][Status][Discuss]
Description
n个集合 m个操作
操作：
1 a b 合并a,b所在集合
2 k 回到第k次操作之后的状态(查询算作操作)
3 a b 询问a,b是否属于同一集合，是则输出1否则输出0
0<n,m<=2*10^4
Input
Output
Sample Input
5 6
1 1 2
3 1 2
2 0
3 1 2
2 1
3 1 2
1 1 2
3 1 2
2 0
3 1 2
2 1
3 1 2
Sample Output
1
0
1
0
1