（前言：我想我需要有人给我讲一遍！！！！！！）
亲爱的qtf感冒了.....我可真是中国好室友qwqqqq
好吧我是不会说打着给她喂药的名号回屋玩手机QAQ
今天算是很不容易的看懂了可持续化并查集...(但还不算很懂
3402 【模板】可持久化并查集
n个集合 m个操作
操作：
-
1 a b合并a,b所在集合 -
2 k回到第k次操作之后的状态(查询算作操作) -
3 a b询问a,b是否属于同一集合，是则输出1否则输出0
解答写在了代码里qwqqqq
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #define max 2000005 using namespace std; int k,l,r,ls[max],rs[max],pos,res,sz,v[max],root[max],i; int n,m;//我也不知道v数组是干什么的... int c;//大概就是存个数? int a,b;//rs和ls就是用来存左右子树的吧QAQ int deep[max]; int read()//快读qwq {int ans = 0;int op = 1;int ch = getchar();while(ch < '0'||ch > '9'){if(ch == '-')op = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){ans *= 10;ans += ch - '0';ch = getchar();}return ans*op; } void build(int &k,int l,int r)//建树 {if(k==0)k = ++sz;//向下传递？ if(l == r){v[k] = l;//如果是子节点 return ;}int mid = (l+r) / 2;build(ls[k],l,mid);build(rs[k],mid+1,r); } void add(int k,int l,int r,int pos)//添加 {if(l == r){deep[k]++;//加深 return ;}int mid = (l+r) / 2;if(pos <= mid){add(ls[k],l,mid,pos);}else add(rs[k],mid + 1,r,pos); } int query(int k,int l,int r,int res)//查询 {if(l == r)return k;//到达子节点 也就是无法继续查询 int mid = (l + r) / 2;if(res <= mid)return query(ls[k],l,mid,res);else return query(rs[k],mid + 1,r,res); } void modify(int l,int r,int x,int &y,int pos,int val)//修改 x,y是要修改的数？ {y = ++sz;if(l == r){v[y] = val;//val可不是价值的意思 deep[y] = deep[x];return ;}ls[y] = ls[x];rs[y] = rs[x];int mid = (l + r) / 2;if(pos <= mid){modify(l,mid,ls[x],ls[y],pos,val);}elsemodify(mid + 1,r,rs[x],rs[y],pos,val); } int find(int k,int x) {int p = query(k,1,n,x);//在1-n的范围里 找以k为节点的x? if(x == v[p]){return p;}return find (k,v[p]);//我我我已经解释不了了.... } int main(){//下面就很好理解啦 n = read();//我就不说啦 m = read();build(root[0],1,n);for(int i = 1;i <= m;++ i){c = read();if(c == 1){a = read();b = read();root[i] = root[i-1];int p = find(root[i],a);int q = find(root[i],b);if(v[p] == v[q])continue;if(deep[p] > deep[q]){swap(p,q);}modify(1,n,root[i-1],root[i],v[p],v[q]);if(deep[q] == deep[p])add(root[i],1,n,v[q]);}if(c == 2){k = read();root[i] = root[k];}if(c == 3){root[i] = root[i-1];a = read();b = read();int p = find(root[i],a);int q = find(root[i],b);if(v[p] == v[q]){printf("1\n");}else printf("0\n");}}return 0; }
要是有人会的话....
能给我讲一下嘛
（好吧 我应该在做白日梦QAQ