← 返回题目列表

AtCoder · abc403_e

H. 禁止前缀

中文机器翻译题面 查看原题

分数: 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