n个集合 m个操作 操作： 1 a b 合并a,b所在集合 2 k 回到第k次操作之后的状态(查询算作操作) 3 a b 询问a,b是否属于同一集合，是则输出1否则输出0
0<n,m<=2*10^5 强制在线。
这两题一题都一样，另一题比较水，nm只有2*10^4,允许离线.....
做法很简单，把数组当作可持久化线段树那么维护，每个表示区间的节点都不存东西，每次只要新建log个节点。
我交水的那道过不去，绝望的时候我交了一发加强版居然A了，根据我多年的经验一定是有特殊数据的坑，特判了一波终于过了。
用了启发式合并之后复杂度nlog^2n
#include<iostream> #include<cstdio> #define MN 20000000 #define MM 200000 using namespace std; 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 cnt=0,n,m,last=0,rt[MM+5],cc; struct data{ int x,size; }s[MM*3+5]; struct TREE{ int l,r; data *x; }T[MN]; void build(int x,int l,int r) { if(l==r){T[x].x=&s[l];return;} int mid=l+r>>1; build(T[x].l=(++cnt),l,mid); build(T[x].r=(++cnt),mid+1,r); } data*get(int x,int k,int l=1,int r=n) { if(l==r)return T[x].x; int mid=l+r>>1; if(k<=mid) return get(T[x].l,k,l,mid); else return get(T[x].r,k,mid+1,r); } data getfa(int x,int r) { data y=*get(r,x),ans=y; if(!y.x)return (data){x,ans.size}; while(y.x) {ans=y;y=*get(r,y.x);} return (data){ans.x,y.size}; } void ins(int x,int dep,int k) { int l=1,r=n;int nx=rt[dep]=++cnt; while(l<r) { int mid=l+r>>1; if(k<=mid) { T[nx].r=T[x].r;T[nx].l=++cnt; nx=T[nx].l;x=T[x].l;r=mid; } else { T[nx].l=T[x].l;T[nx].r=++cnt; nx=T[nx].r;x=T[x].r;l=mid+1; } } T[nx].x=&s[cc]; } int main() { cc=n=read();m=read(); for(int i=1;i<=n;i++)s[i]=(data){0,1}; build(++cnt,1,n);rt[0]=1; for(int i=1;i<=m;i++) { int a=read(),b=read()^last; if(a==2) rt[i]=rt[b]; else { int c=read()^last; if(a==3) printf("%d ",last=(getfa(b,rt[i-1]).x==getfa(c,rt[i-1]).x)),rt[i]=rt[i-1]; else { data x=getfa(b,rt[i-1]),y=getfa(c,rt[i-1]); if(x.x==y.x){rt[i]=rt[i-1];continue;} if(x.size>y.size)swap(x,y); s[++cc]=(data){y.x,x.size};ins(rt[i-1],i,x.x); s[++cc]=(data){0,x.size+y.size};ins(rt[i],i,y.x); } } } return 0; }