跪毛主力和zky大神

本题是两位大神+主力出的，所以我这种渣渣只好写渣渣算法了

开始不会做，然后毛主力大发慈悲和我说可以用线段树模拟数组，

然后我就很高兴地谢了个主席树

然后re了

然后调了半个小时发现数组开小了，囧

于是就连A两题。。（本来就差不多的）

3673代码（因为3674因为强制在线有个加密没啥用就不发了）

#include<cstdio>
using namespace std;
struct mjj
{
	int l,r,dad;
	mjj *lc,*rc;
}*root[200010];
int n,m,i,t,x,y,k;
void build0(int l,int r,mjj *&cur)
{
	cur=new mjj;cur->l=l;cur->r=r;
	cur->lc=NULL;cur->rc=NULL;
	if (l==r)
	{
		cur->dad=l;
		return;
	}
	int mid=(l+r)/2;
	build0(l,mid,cur->lc);
	build0(mid+1,r,cur->rc);
}
void change(int d,int k,mjj *&cur,mjj *cur1)
{
	cur=new mjj;cur->l=cur1->l;cur->r=cur1->r;
	cur->lc=NULL;cur->rc=NULL;
	if (cur->l==cur->r){cur->dad=d;return;}
	int mid=(cur->l+cur->r)/2;
	if (k>mid)cur->lc=cur1->lc,change(d,k,cur->rc,cur1->rc);	
	if (k<=mid)cur->rc=cur1->rc,change(d,k,cur->lc,cur1->lc);
}
int find1(int x,mjj *cur)
{
	if (cur->l==cur->r)return cur->dad;
	int mid=(cur->l+cur->r)/2;
	if (x<=mid)return find1(x,cur->lc);
	if (x>mid)return find1(x,cur->rc);
}
int find(int x,int y)
{
	int dd=find1(x,root[y]);
	if (dd==x)return x;
	return find(dd,y);
}
int main()
{
	/*freopen("3673.in","r",stdin);
	freopen("3673.out","w",stdout);*/
	scanf("%d%d",&n,&m);build0(1,n,root[0]);
	for (i=1;i<=m;i++)
	{
		scanf("%d",&t);root[i]=root[i-1];
		if (t==1)
		{
			scanf("%d%d",&x,&y);
			change(find(x,i),find(y,i),root[i],root[i-1]);
		}
		if (t==2)scanf("%d",&k),root[i]=root[k];
		if (t==3)
		{
			scanf("%d%d",&x,&y);
			printf("%d\n",find(x,i)==find(y,i));
		}
	}
}