Description：

三个操作：加入一个数字串。询问一个字符串是否在字符集中。将串 $A$ 和串 $B$ 互相纠缠，即若 $A+D$ 在信息集中， $B+D$ 也在信息集中。

$一和三操作之和\le2050$ $总操作之和\le10^5$

Solution：

首先发现如果把信息集建成一棵 $trie$ ，那么 $3$ 操作就是把这两个字符串对应的节点合并，即 $A$ 所有的转移 $B$ 也有。问题就变成如何合并两个节点，可以用并查集维护合并，每次把一个的并查集父亲设成另一个，并递归合并所有的转移，如果一个为空那么返回，注意在递归时 $b$ 不能更改，因为 $b$ 的并查集父亲已经改变，如果修改了 $b$ 那 $b$ 的转移就找不到了。每次转移时用并查集祖先的转移。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MAXL 1000100

int n;

char c[MAXL * 8];

struct node

{

	int tr[10];

	bool tag;

}t[MAXL];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

int f[MAXL];

int find(int x){return (f[x] == x ? x : f[x] = find(f[x]));}

void insert(char c[])

{

	int cur = root;

	int l = strlen(c + 1);

	for(int i = 1;i <= l;++i)

	{

		if(t[cur].tr[c[i] - '0'] == 0)

			t[cur].tr[c[i] - '0'] = newnode();

		cur = find(t[cur].tr[c[i] - '0']);

	}

	t[cur].tag = true;

	return;

}

bool query(char c[])

{

	int cur = root;

	int l = strlen(c + 1);

	for(int i = 1;i <= l;++i)

	{

		if(t[cur].tr[c[i] - '0'] == 0)

			return false;

		cur = find(t[cur].tr[c[i] - '0']);

	}

	return t[cur].tag;

}

int &getnode(char c[])

{

	int cur = root;

	int l = strlen(c + 1);

	for(int i = 1;i < l;++i)

	{

		if(t[cur].tr[c[i] - '0'] == 0)

			t[cur].tr[c[i] - '0'] = newnode();

		cur = find(t[cur].tr[c[i] - '0']);

	}

	return t[cur].tr[c[l] - '0'];

}

void merge(int &a,int &b,bool flag)

{

	a = find(a);int y = find(b);

	if(a == 0 && y == 0)

	{

		if(flag)a = b = newnode();

		return;

	}

	if(a == y)return;

	if(a == 0){a = y;return;}

	if(b == 0){b = a;return;}

	f[y] = a;

	if(t[y].tag)t[a].tag = true;

	for(int i = 0;i < 10;++i)

	{

		merge(t[a].tr[i],t[y].tr[i],false);

		a = find(a);

	}

	return;

}

void connect()

{

	int &a = getnode(c);

	scanf("%s",c + 1);

	int &b = getnode(c);

	merge(a,b,true);

	return;

}

int main()

{

	freopen("quantum.in","r",stdin);

	freopen("quantum.out","w",stdout);

    root = newnode();

    for(int i = 1;i < MAXL;++i)f[i] = i;

	scanf("%d",&n);

	int t;

	for(int i = 1;i <= n;++i)

	{

		scanf("%d%s",&t,c + 1);

		if(t == 1)insert(c);

		if(t == 2)puts(query(c) ? "1" : "0");

		if(t == 3)connect();

	}

	fclose(stdin);

	fclose(stdout);

	return 0;

}