深圳均安网站制作,网站开发中为什么有两个控制层,网站图片多 如何优化,亚马逊站外推广网站题目链接 题目描述
给定 nnn 个集合#xff0c;第 iii 个集合内初始状态下只有一个数#xff0c;为 iii。
有 mmm 次操作。操作分为 333 种#xff1a; 1 a b 合并 a,ba,ba,b 所在集合#xff1b; 2 k 回到第 kkk 次操作#xff08;执行三种操作中的任意一种都记为一次… 题目链接 题目描述
给定 nnn 个集合第 iii 个集合内初始状态下只有一个数为 iii。
有 mmm 次操作。操作分为 333 种 1 a b 合并 a,ba,ba,b 所在集合 2 k 回到第 kkk 次操作执行三种操作中的任意一种都记为一次操作之后的状态 3 a b 询问 a,ba,ba,b 是否属于同一集合如果是则输出 1 否则输出 0。
输入格式
第一行两个整数n,mn,mn,m。
接下来 mmm 行每行先输入一个数 optoptopt。若 opt2opt2opt2 则再输入一个整数 kkk否则再输入两个整数 a,ba,ba,b描述一次操作。
输出格式
对每个操作 333输出一行一个整数表示答案。
输入输出样例
输入 #1
5 6
1 1 2
3 1 2
2 0
3 1 2
2 1
3 1 2输出 #1
1
0
1说明/提示
对于 100%100\%100% 的数据1≤n≤1051≤m≤2×1051\le n\le 10^51\le m\le 2\times 10^51≤n≤1051≤m≤2×105。 Solution
模板题可以通过 可持久化数组 启发式合并 /// 按秩合并 实现。
Code
#includecstdio
#includealgorithm
using namespace std;
const int maxn300010;
struct SegmentTree{int lc,rc,l,r,fa,siz;
}tr[maxn*40];
int n,m,tot,root[maxn];
inline int build(int l,int r){int utot,mid(lr)1;tr[u].ll;tr[u].rr;if(lr){tr[u].fal;tr[u].siz1;return u;}tr[u].lcbuild(l,mid);tr[u].rcbuild(mid1,r);return u;
}
inline int query(int u,int a){if(tr[u].ltr[u].r)return u;int mid(tr[u].ltr[u].r)1;if(amid)return query(tr[u].lc,a);else return query(tr[u].rc,a);
}
inline int find(int v,int x){int pquery(root[v],x);return tr[p].fax?x:find(v,tr[p].fa);
}
inline int merge(int p,int pos,int fa){int utot;tr[u].ltr[p].l;tr[u].rtr[p].r;if(tr[u].ltr[u].r){tr[u].fafa;return u;}int mid(tr[u].ltr[u].r)1;if(posmid){tr[u].rctr[p].rc;tr[u].lcmerge(tr[p].lc,pos,fa);}else{tr[u].lctr[p].lc;tr[u].rcmerge(tr[p].rc,pos,fa);}return u;
}
inline int add(int p,int pos,int d){int utot;tr[u].ltr[p].l;tr[u].rtr[p].r;if(tr[u].ltr[u].r){tr[u].fatr[p].fa;tr[u].siztr[p].sizd;return u;}int mid(tr[u].ltr[u].r)1;if(posmid){tr[u].rctr[p].rc;tr[u].lcadd(tr[p].lc,pos,d);}else{tr[u].lctr[p].lc;tr[u].rcadd(tr[p].rc,pos,d);}return u;
}
int main(){scanf(%d%d,n,m);root[0]build(1,n);for(int i1;im;i){int opt,a,b;scanf(%d,opt);if(opt1){scanf(%d%d,a,b);afind(i-1,a);bfind(i-1,b);if(ab){root[i]root[i-1];continue;}int xquery(root[i-1],a),yquery(root[i-1],b);if(tr[x].siztr[y].siz)swap(x,y),swap(a,b);root[i]merge(root[i-1],a,b);root[i]add(root[i],b,tr[x].siz);}else if(opt2){scanf(%d,a);root[i]root[a];}else{scanf(%d%d,a,b);root[i]root[i-1];printf(%d\n,find(i,a)find(i,b));}}return 0;
}
