3674: 可持久化并查集加强版
Time Limit: 15 Sec Memory Limit: 256 MBSubmit: 1053 Solved: 381
[Submit][Status][Discuss]
Description
Description：
自从zkysb出了可持久化并查集后……
hzwer:乱写能AC，暴力踩标程
KuribohG：我不路径压缩就过了！
ndsf：暴力就可以轻松虐！
zky:……
n个集合 m个操作
操作：
1 a b 合并a,b所在集合
2 k 回到第k次操作之后的状态(查询算作操作)
3 a b 询问a,b是否属于同一集合，是则输出1否则输出0
请注意本题采用强制在线,所给的a,b,k均经过加密,加密方法为x = x xor lastans,lastans的初始值为0
0<n,m<=2*10^5
Input
Output
Sample Input
5 6
1 1 2
3 1 2
2 1
3 0 3
2 1
3 1 2
Sample Output
1
0
1
HINT
Source
好吧，我承认我确实打可持久化数据结构有点上瘾了，因为它的魅力着实让我欲罢不能。。。
回归本题。
此题我们只要维护每一次的并查集的fa数组，由于时间问题，我们还需要维护连通块中点的个数来按秩合并。要维护数组，我们可以用可持久化线段树来维护，线段树的叶子节点就是这个数组，这样就可以维护每次的并查集了。
代码：
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,opt,x,y,x1,x2,ans,cnt,root[210010];
struct node{int l,r,fa,num;}tr[15000010];
void change(int l,int r,int &p,int x,int fa,int num)
{
tr[++cnt]=tr[p];p=cnt;
if (l==r){tr[p].fa=fa;tr[p].num=num;return;}
int mid=(l+r)>>1;
if (x<=mid) change(l,mid,tr[p].l,x,fa,num);else change(mid+1,r,tr[p].r,x,fa,num);
}
int ask(int l,int r,int p,int x)
{
if (l==r) return p;
int mid=(l+r)>>1;
if (x<=mid) return ask(l,mid,tr[p].l,x);else return ask(mid+1,r,tr[p].r,x);
}
int getfather(int p,int x)
{
int t=ask(1,n,p,x);
if (tr[t].fa==x) return t;else return getfather(p,tr[t].fa);
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
change(1,n,root[0],i,i,1);
for (int i=1;i<=m;i++)
{
scanf("%d",&opt);
root[i]=root[i-1];
if (opt==1)
{
scanf("%d%d",&x,&y);
x^=ans;y^=ans;
x1=getfather(root[i],x);x2=getfather(root[i],y);
if (tr[x1].fa==tr[x2].fa) continue;
if (tr[x1].num>tr[x2].num) swap(x1,x2);
change(1,n,root[i],tr[x1].fa,tr[x2].fa,0);
change(1,n,root[i],tr[x2].fa,tr[x2].fa,tr[x2].num+tr[x1].num);
}else
if (opt==2)
{
scanf("%d",&x);
x^=ans;
root[i]=root[x];
}else
{
scanf("%d%d",&x,&y);
x^=ans;y^=ans;
x1=getfather(root[i],x);x2=getfather(root[i],y);
if (tr[x1].fa==tr[x2].fa) ans=1;else ans=0;
printf("%d\n",ans);
}
}
}
评论 (0)
