题目概述
有
n
个点和 m 个操作，操作有：
合并两个点。回到第
k
<script type="math/tex" id="MathJax-Element-5">k</script> 次操作。判断两个点是否联通。
解题报告
题目描述（题目名称）就是让你实现一个可持久化并查集。
好像没有这种操作？由于我们会发现并查集就是个数组，所以我们可以用主席树实现可持久化数组。
然后就好了……我就是在水博客……
网上有些说不能用路径压缩，实际上是可以的，只不过空间有点大，看代码吧QAQ。
示例程序
#include<cstdio>
using namespace std;
const int maxm=
200000,maxt=
10000000;
int n,m,te,lstans;
struct node {node* son[
2];
int x;};
typedef node* P_node;
node tem[maxt+
5];P_node ro[maxm+
5],si=tem;
#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc()
{
static char buf[
100000],*l=buf,*r=buf;
if (l==r) r=(l=buf)+fread(buf,
1,
100000,stdin);
if (l==r)
return EOF;
else return *l++;
}
inline int readi(
int &x)
{
int tot=
0,f=
1;
char ch=readc(),lst=
'+';
while (
'9'<ch||ch<
'0') {
if (ch==EOF)
return EOF;lst=ch;ch=readc();}
if (lst==
'-') f=-f;
while (
'0'<=ch&&ch<=
'9') tot=(tot<<
3)+(tot<<
1)+ch-
48,ch=readc();
return x=tot*f,Eoln(ch);
}
P_node Build(
int L,
int R)
{
P_node now=si++;
int mid=L+(R-L>>
1);
if (L==R)
return now->x=mid,now;
now->son[
0]=Build(L,mid);now->son[
1]=Build(mid+
1,R);
return now;
}
P_node Insert(P_node p,
int pos,
int x,
int l=
1,
int r=n)
{
P_node now=si++;
int mid=l+(r-l>>
1);
now->son[
0]=p->son[
0];now->son[
1]=p->son[
1];
if (l==r) now->x=x;
else
if (pos<=mid) now->son[
0]=Insert(p->son[
0],pos,x,l,mid);
else
now->son[
1]=Insert(p->son[
1],pos,x,mid+
1,r);
return now;
}
int Ask(P_node p,
int pos,
int l=
1,
int r=n)
{
if (l==r)
return p->x;
int mid=l+(r-l>>
1);
if (pos<=mid)
return Ask(p->son[
0],pos,l,mid);
else
return Ask(p->son[
1],pos,mid+
1,r);
}
int getfa(P_node &p,
int x)
{
int fx=Ask(p,x);
if (fx==x)
return x;
fx=getfa(p,fx);p=Insert(p,x,fx);
return fx;
}
inline void Add(
int ID,
int x,
int y)
{
int fx=getfa(ro[ID-
1],x),fy=getfa(ro[ID-
1],y);
if (fx==fy) {ro[ID]=ro[ID-
1];
return;}
ro[ID]=Insert(ro[ID-
1],fx,fy);
}
#define check(x,y) (getfa(ro[m],x)==getfa(ro[m],y))
inline void Print(
int x,
int y)
{
m++;ro[m]=ro[m-
1];
putchar((lstans=check(x,y))+
48);
putchar(
'\n');
}
int main()
{
freopen(
"program.in",
"r",stdin);
freopen(
"program.out",
"w",stdout);
readi(n);ro[
0]=Build(
1,n);
for (readi(te);te;te--)
{
int td,x,y;readi(td);readi(x);x^=lstans;
if (td==
1) readi(y),y^=lstans,Add(++m,x,y);
else
if (td==
2) ro[++m]=ro[x];
else
readi(y),y^=lstans,Print(x,y);
}
return 0;
}
