3673: 可持久化并查集 by zky

Time Limit: 5 Sec  Memory Limit: 128 MB

Submit: 2170  Solved: 978

[][][]

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

Sample Output

1

0

1

HINT

 

Source

//（暴力）用rope实现可持久化数组#include
      
       #include
       
        using namespace std;using namespace __gnu_cxx;const int N=2e4+5;rope
        
          *h[N];int n,m;inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}    return x*f;}int id,a,b,fx,fy;int find(int x){    int fax=h[id]->at(x);    if(fax==x) return x;    fax=find(fax);    h[id]->insert(x,fax);    h[id]->erase(x+1,1);    return fax;}inline void merge(){    fx=find(a);fy=find(b);    if(fx!=fy){        h[id]->insert(fx,fy);        h[id]->erase(fx+1,1);    }}inline bool isone(){    fx=find(a);fy=find(b);    return fx==fy;}int main(){    n=10;    n=read();m=read();    h[0]=new rope
         
           ();    for(int i=0;i<=n;i++) h[0]->push_back(i);    for(int i=1,opt;i<=m;i++){        opt=read();a=read();        if(opt&1) b=read();        h[i]=new rope
          
            (*h[opt&1?i-1:a]);        id=i;        if(opt==1){            merge();        }        if(opt==3){            printf("%d\n",isone());        }    }    return 0;}