A7327. 字典树模板
编程题
普及/提高-
知识点
题目描述
小明有一个单词仓库，仓库中一开始没有任何单词。
接下来会进行 $Q$ 次操作，每次操作有以下三种类型：
-
-
-
注意，同一个单词可以被插入多次，每次插入都要计入答案。
你需要对每个查询操作输出答案。
接下来会进行 $Q$ 次操作，每次操作有以下三种类型：
-
1 s：向仓库中插入一个单词 $s$；-
2 s：查询单词 $s$ 在仓库中完整出现了多少次；-
3 s：查询仓库中有多少个单词以 $s$ 作为前缀。注意，同一个单词可以被插入多次，每次插入都要计入答案。
你需要对每个查询操作输出答案。
输入格式
第一行输入一个整数 $Q$，表示操作次数。
接下来 $Q$ 行，每行输入一个整数 $op$ 和一个字符串 $s$，表示一次操作。
其中：
- 当 $op=1$ 时，表示插入字符串 $s$；
- 当 $op=2$ 时，表示查询字符串 $s$ 完整出现了多少次；
- 当 $op=3$ 时，表示查询有多少个字符串以 $s$ 为前缀。
接下来 $Q$ 行，每行输入一个整数 $op$ 和一个字符串 $s$，表示一次操作。
其中：
- 当 $op=1$ 时，表示插入字符串 $s$；
- 当 $op=2$ 时，表示查询字符串 $s$ 完整出现了多少次；
- 当 $op=3$ 时，表示查询有多少个字符串以 $s$ 为前缀。
输出格式
对于每个 $op=2$ 或 $op=3$ 的操作，输出一行一个整数，表示查询结果。
输入输出样例
输入 #1
10 1 apple 1 app 1 apple 3 app 2 apple 2 app 2 appl 1 banana 3 ba 3 a
输出 #1
3 2 1 0 1 3
说明/提示
## 样例解释
一开始仓库为空。
插入
-
-
所以：
- 以
-
-
-
后来插入
- 以
- 以
## 数据范围
对于所有数据，满足：
- $1\le Q\le 2\times 10^5$；
- $1\le |s|\le 50$；
- 字符串 $s$ 仅由小写英文字母组成；
- 所有输入字符串的总长度不超过 $10^6$。
一开始仓库为空。
插入
apple、app、apple 后，仓库中有：-
apple 出现 $2$ 次；-
app 出现 $1$ 次。所以：
- 以
app 为前缀的单词有 apple、app、apple，共 $3$ 个；-
apple 完整出现了 $2$ 次；-
app 完整出现了 $1$ 次；-
appl 没有完整出现过，答案为 $0$。后来插入
banana，所以：- 以
ba 为前缀的单词有 $1$ 个；- 以
a 为前缀的单词有 $3$ 个。## 数据范围
对于所有数据，满足：
- $1\le Q\le 2\times 10^5$；
- $1\le |s|\le 50$；
- 字符串 $s$ 仅由小写英文字母组成；
- 所有输入字符串的总长度不超过 $10^6$。