分数: 500 点
问题陈述
有两个多重字符串集, X 和 Y,最初都是空的。
你被给予 Q 查询按顺序处理。在 i-第查询,您收到一个整数 T_i 和一个字符串 S_i。如果 T_i=1,插入 S_i 进入 X;如果 T_i=2,插入 S_i 进入 Y.
处理每个查询后,打印此值:
- 中的字符串数 Y 没有以下元素 X 作为前缀。
约束
- Q 是介于 1 和 2 \times 10^5,包括在内。
- T_i \in \{1,2\}
- 每个 S_i 是长度介于 1 和 5\times 10^5,包含在内,由小写英文字母组成。
- \displaystyle \sum_{i=1}^Q |S_i| \leq 5 \times 10^5
输入
输入由标准输入按以下格式给出:
Q T_1\ S_1 T_2\ S_2 \vdots T_Q\ S_Q
输出
打印 Q 行。的 i第行 (1 \leq i \leq Q) 应包含处理后的计数 i-第一个查询。
示例输入 1
4 1 at 2 watcoder 2 atcoder 1 wa
示例输出 1
0 1 1 0
处理查询后的计数 i=1,2,3,4 如下。
- i=1: Y 为空,因此计数为 0.
- i=2:
watcoder没有以下元素 X 作为前缀,因此计数为 1. - i=3:
watcoder没有以下元素 X 作为前缀,而atcoder有at作为前缀,因此计数为 1. - i=4:
watcoder有wa作为前缀,并且atcoder有at作为前缀,因此计数为 0.
示例输入 2
10 1 w 1 avko 2 atcoder 1 bzginn 2 beginner 1 atco 2 contest 1 ntxcdg 1 atc 1 contest
示例输出 2
0 0 1 1 2 1 2 2 2 1