/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
文字列の多重集合 X,Y があります。はじめ、両方ともに空です。
Q 個のクエリが与えられるので、順に処理してください。i 番目のクエリでは、整数 T_i と文字列 S_i が与えられるので、T_i=1 ならば X に S_i を追加し、T_i=2 ならば Y に S_i を追加してください。
各クエリの処理後、以下の値を出力してください。
- 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
Score : 500 points
Problem Statement
There are two multisets of strings, X and Y, both initially empty.
You are given Q queries to process in order. In the i-th query, you receive an integer T_i and a string S_i. If T_i=1, insert S_i into X; if T_i=2, insert S_i into Y.
After processing each query, print this value:
- the number of strings in Y that have no element of X as a prefix.
Constraints
- Q is an integer between 1 and 2 \times 10^5, inclusive.
- T_i \in \{1,2\}
- Each S_i is a string of length between 1 and 5\times 10^5, inclusive, consisting of lowercase English letters.
- \displaystyle \sum_{i=1}^Q |S_i| \leq 5 \times 10^5
Input
The input is given from Standard Input in the following format:
Q T_1\ S_1 T_2\ S_2 \vdots T_Q\ S_Q
Output
Print Q lines. The i-th line (1 \leq i \leq Q) should contain the count after processing the i-th query.
Sample Input 1
4 1 at 2 watcoder 2 atcoder 1 wa
Sample Output 1
0 1 1 0
The counts after processing the queries for i=1,2,3,4 are as follows.
- i=1: Y is empty, so the count is 0.
- i=2:
watcoderhas no element of X as a prefix, so the count is 1. - i=3:
watcoderhas no element of X as a prefix, whileatcoderhasatas a prefix, so the count is 1. - i=4:
watcoderhaswaas a prefix, andatcoderhasatas a prefix, so the count is 0.
Sample Input 2
10 1 w 1 avko 2 atcoder 1 bzginn 2 beginner 1 atco 2 contest 1 ntxcdg 1 atc 1 contest
Sample Output 2
0 0 1 1 2 1 2 2 2 1