题意

问题描述

万能的红太阳J 君正在研究量子信息的纠缠。

具体来说，J 君有一个初始为空的信息集。她会进行m 次操作，有时，她会向信息集内加入一个长度不超过L 的的数字串(一个数字串为一个仅由0 到9 组成的非空字符串)，有时她会给出一个数字串，询问这个数字串是否包含在她的信息集中，有时她会选取两个长度不超过L 的数字串，使她们在信息集内互相纠缠。

两个数字串A 和B 互相纠缠代表，对于信息集中的任意串A+C，需满足B +C 也在信息集中，对于信息集中的任意串B + D，需满足A + D 也在信息集中(其中+ 代表字符串顺序连接，C;D 可能是空串)，因此一次纠缠操作可能导致若干个数字串(可能为无穷多个) 被加入信息集中。

由于两个数字串的纠缠是一种状态，在纠缠后的任何时刻都需满足以上性质，因此第一次纠缠操作之后的任何添加操作都可能导致大于1 个(可能为无穷多个) 数字串被加入信息集。

你需要做的就是回答J 君的所有询问。

输入格式

第一行包含一个正整数m，代表操作数。

接下来m 行，每行可能有以下形式：

1 s 代表将数字串s 加入信息集中

2 s 代表询问数字串s 是否在信息集中

3 a b 代表使数字串a 和b 互相纠缠

输出格式

对于每一个2 操作，如果询问串不在集合中，请输出一行一个整数0，否则输出一行一个整数1。

样例输入

11

1 123

2 123

2 0

3 12 13

1 124

2 133

2 134

2 13

3 1 11

2 111

2 11111111111111111111111124

样例输出

1

0

1

1

0

0

1

数据规模与约定

100% 的数据满足\(m \leq 10^5, c \leq 2050, S \leq 8 \times 10^6,L \leq 50, P \equiv m \mod 10\)。

其中c 代表1 操作与3 操作次数之和，S 代表询问字符串的总长度。

分析

首先考虑没有3 操作的情况，我们很容易想到使用一个字典树维护这个集合。

接下来考虑3 操作，对于每个3 操作，我们只需要递归合并上述字典树上的两个节点即可。

时间复杂度\(O(c^2L + S)\)

这时间复杂度我也不知道是怎么回事。

代码

#define yuki(x, y) for(int i = x, __yuki__ = y; i < __yuki__; ++i)

#define yukj(x, y) for(int j = x, __yukj__ = y; j < __yukj__; ++j)

#define yukii(x, y) for(int i = x, __yukii__ = y; i <= __yukii__; ++i)

#define yukji(x, y) for(int j = x, __yukji__ = y; j <= __yukji__; ++j)

#define yuk(x, y, z) for(int x = y, __yui__ = z; x < __yui__; ++x)

#define yui(x, y, z) for(int x = y, __yuk__ = z; x >= __yuk__; --x)

#define sclr(x) memset(x, 0, sizeof(x))

#define sclr1(x) memset(x, -1, sizeof(x))

#define scl(x, y) memset(x, y, sizeof(x))

#define ft first

#define sc second

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cassert>

using namespace std;

typedef long long lol;

const int maxp = 1000100;

int n, m, alc, refl[1000100], fre[1000100], trans[1000100][10], root;

char buf[8000100];

bool mk[1000100];

int gf(int x)

{

	return refl[x] == x ? x : (refl[x] = gf(refl[x]));

}

void init()

{

	yuki(1, maxp) refl[i] = i;

	root = ++alc;

}

void insert(char *ch)

{

	int cur = root;

	while(*ch)

	{

		int x = *ch++-'0';

		if(!trans[cur][x]) trans[cur][x] = ++alc;

		cur = gf(trans[cur][x]);

	}

	mk[cur] = true;

}

bool ask(char *ch)

{

	int cur = root;

	while(*ch)

	{

		int x = *ch++-'0';

		if(!trans[cur][x]) return false;

		cur = gf(trans[cur][x]);

	}

	return mk[cur];

}

int &getnode(char *s)

{

	int cur = root;

	int l = strlen(s);

	yuki(0, l-1)

	{

		int x = s[i]-'0';

		if(!trans[cur][x]) trans[cur][x] = ++alc;

		cur = gf(trans[cur][x]);

	}

	return trans[cur][s[l-1]-'0'];

}

void merge(int &a, int &b, bool flag) // 类似线段树启发式合并

{

	a = gf(a);

	int y = gf(b); // 不用重新定义y

	if(!a && !y)

	{

		if(flag) a = b = ++alc; // 都没有要补上，为了以后的修改

		return;

	}

	else if(a == y) // 已经相同就不用补了

		return;

	if(!a) // 单空返回

	{

		a = y;

		return;

	}

	else if(!b)

	{

		b = a;

		return;

	}

	refl[y] = a; // 合并子树的标记

	if(mk[y]) mk[a] = true; // 合并单词的存在性

	yuki(0, 10)

	{

		merge(trans[a][i], trans[y][i], false);

		a = gf(a); // 后代可能会对祖先取并

	}

}

void cond()

{

	int &a = getnode(buf);

	scanf("%s", buf);

	int &b = getnode(buf);

	merge(a, b, true);

}

int main(int argc, char **argv)

{

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

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

	init();

	scanf("%d", &n);

	int t;

	while(n--)

	{

		scanf("%d%s", &t, buf);

		if(t == 1)

			insert(buf);

		else if(t == 2)

			puts(ask(buf) ? "1" : "0");

		else

			cond();

	}

	return 0;

}

巴特西

test20180921 量子纠缠

题意