https://namomo.top:8081/contest/4

String

题意：维护一些 01 串。四种操作：加入一个字符串，权值为 v；删掉所有字符串 s；输出所有以 s 为前缀的字符串的权值之和；把所有形如 sx 的字符串改为 tx，保证 s 与 t 最长公共前缀为空。如果不存在则输出"Not Exist"。

Trie+模拟

直接按照题意模拟。

由于串的长度比较大，所以为了防止下标不够用，可以循环利用删除了的点下标。

维护 val[i]val[i] 表示 Trie 上以 s 为前缀的所有串的权值和。

每次插入时沿路增加 val 值。删除时先判断如果 val 值等于两个儿子的 val 之和，说明串 s 并不存在。若存在则沿路删除 val。

查询时直接找到串 s ，输出它的 val。

最后一个操作需要先找到 s，再找到 t，并把 s 的子树合并到 t 去。所以先找到 s，得到 它的 val，需要把这个值加到 t 到根的路径上，由于 t 可能不存在，所以直接先建出 t，权值为 s 的 val。再合并 s，t，如果 s 有儿子而 t 没有，则直接把 s 的儿子接到 t 去，否则销毁 s 的儿子，把它的 val 值加到 t 的儿子上去，递归进行下去。注意 t 不要被重复加。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e6 + 10;
const ll mod = 1e9 + 7;
int ch[N][2], fa[N];
char s[N], t[N];
int root;
ll val[N];
stack<int>st;
int ins(char s[], ll v) {
	int rt = 0;
	for (int i = 0; s[i]; i++) {
		int bt = s[i] - '0';
		if (!ch[rt][bt]) {
			int u = st.top(); st.pop();
			ch[u][0] = ch[u][1] = 0;
			val[u] = 0;
			ch[rt][bt] = u;
		}
		rt = ch[rt][bt];
		val[rt] += v;
	}
	return rt;
}
int qry(char s[]) {
	int rt = 0;
	for (int i = 0; s[i]; i++) {
		int bt = s[i] - '0';
		if (!ch[rt][bt])return -1;
		rt = ch[rt][bt];
	}
	return rt;
}
void merge(int a, int b) {
	val[b] += val[a];
	if (ch[a][0]) {
		if (!ch[b][0])ch[b][0] = ch[a][0], ch[a][0] = 0;
		else {
			merge(ch[a][0], ch[b][0]);
			st.push(ch[a][0]); ch[a][0] = 0;
		}
	}
	if (ch[a][1]) {
		if (!ch[b][1])ch[b][1] = ch[a][1], ch[a][1] = 0;
		else {
			merge(ch[a][1], ch[b][1]);
			st.push(ch[a][1]); ch[a][1] = 0;
		}
	}
}
int T, tt;
int q;
int main() {
	scanf("%d", &T);
	while (++tt <= T) {
		printf("Case %d\n", tt);
		memset(val, 0, sizeof(val));
		memset(fa, 0, sizeof(fa));
		memset(ch, 0, sizeof(ch));
		while (!st.empty())st.pop();
		for (int i = N - 1; i >= 1; i--)st.push(i);
		root = 0;
		scanf("%d", &q);
		while (q--) {
			char op;
			scanf(" %c", &op);
			if (op == 'I') {
				ll v;
				scanf("%s%lld", s, &v);
				ins(s, v);
			}
			else if (op == 'Q') {
				scanf("%s", s);
				int u = qry(s);
				if (u == -1)puts("0");
				else printf("%lld\n", val[u]);
			}
			else if (op == 'D') {
				scanf("%s", s);
				int u = qry(s);
				if (u == -1)puts("Not Exist");
				else {
					ll tmp = val[u] - val[ch[u][0]] - val[ch[u][1]];
					if (!tmp)puts("Not Exist");
					else {
						int rt = 0;
						for (int i = 0; s[i]; i++) {
							rt = ch[rt][s[i] - '0'];
							val[rt] -= tmp;
						}
					}
				}
			}
			else {
				scanf("%s%s", s, t);
				int a = qry(s);
				if (a == -1 || !val[a]) { puts("Not Exist"); continue; }
				ll tmp = val[a];
				int rt = 0;
				for (int i = 0; i < (int)strlen(s) - 1; i++) {
					rt = ch[rt][s[i] - '0'];
					val[rt] -= tmp;
				}
				ch[rt][s[(int)strlen(s) - 1] - '0'] = 0;
				int b = ins(t, tmp);
				val[b] -= tmp;
				merge(a, b);
			}
		}
	}
	return 0;
}