这个题竟然没有用什么新算法，就是用主席树随便搞搞就过了。。。代码好像也很好理解。
题干：
n个集合 m个操作 操作： 1 a b 合并a,b所在集合 2 k 回到第k次操作之后的状态(查询算作操作) 3 a b 询问a,b是否属于同一集合，是则输出1否则输出0 输入输出格式 输入格式： 输出格式： 输入输出样例 输入样例#1： 5 6 1 1 2 3 1 2 2 0 3 1 2 2 1 3 1 2 输出样例#1： 1 0 1 说明 1 le n le 10^5, 1 le m le 2 imes 10^51≤n≤10 5 ,1≤m≤2×10 5 By zky 出题人大神犇
代码：
#include<iostream> #include<cstdio> #include<cmath> #include<ctime> #include<queue> #include<algorithm> #include<cstring> using namespace std; #define duke(i,a,n) for(register int i = a;i <= n;i++) #define lv(i,a,n) for(register int i = a;i >= n;i--) #define clean(a) memset(a,0,sizeof(a)) const int INF = 1 << 30; typedef long long ll; typedef double db; template <class T> void read(T &x) { char c; bool op = 0; while(c = getchar(), c < '0' || c > '9') if(c == '-') op = 1; x = c - '0'; while(c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; if(op) x = -x; } template <class T> void write(T x) { if(x < 0) putchar('-'), x = -x; if(x >= 10) write(x / 10); putchar('0' + x % 10); } const int N = 200010; struct node { int l,r; }tree[N * 30]; int rt[N * 30],tot = 0,fa[N * 30],dep[N * 30]; int n,m; void build(int &now,int l,int r) { now = ++tot; if(l == r) { fa[now] = l; return; } int mid = (l + r) >> 1; build(tree[now].l,l,mid); build(tree[now].r,mid + 1,r); } void update(int &now,int lst,int l,int r,int pos,int ff) { now = ++tot; if(l == r) { fa[now] = ff; dep[now] = dep[lst]; return; } tree[now] = tree[lst]; int mid = (l + r) >> 1; if(pos <= mid) update(tree[now].l,tree[lst].l,l,mid,pos,ff); else update(tree[now].r,tree[lst].r,mid + 1,r,pos,ff); } int query(int now,int l,int r,int pos) { if(l == r) { return now; } int mid = (l + r) >> 1; if(pos <= mid) return query(tree[now].l,l,mid,pos); else return query(tree[now].r,mid + 1,r,pos); } void add(int now,int l,int r,int pos) { if(l == r) { ++dep[now]; return; } int mid = (l + r) >> 1; if(pos <= mid) add(tree[now].l,l,mid,pos); else add(tree[now].r,mid + 1,r,pos); } int find_fa(int now,int x) { int ff = query(now,1,n,x); if(x == fa[ff]) return ff; return find_fa(now,fa[ff]); } int main() { read(n);read(m); build(rt[0],1,n); int opt,a,b,k; duke(i,1,m) { read(opt); if(opt == 1) { rt[i] = rt[i - 1]; read(a);read(b); int f1 = find_fa(rt[i],a); int f2 = find_fa(rt[i],b); if(fa[f1] == fa[f2]) continue; if(dep[f1] > dep[f2]) swap(f1,f2); update(rt[i],rt[i - 1],1,n,fa[f1],fa[f2]); if(dep[f1] == dep[f2]) add(rt[i],1,n,fa[f2]); } if(opt == 2) { read(k); rt[i] = rt[k]; } if(opt == 3) { rt[i] = rt[i - 1]; read(a);read(b); int f1 = find_fa(rt[i],a); int f2 = find_fa(rt[i],b); if(f1 == f2) puts("1"); else puts("0"); } } return 0; }