Trie 木を使わず実装が単純な \(O(\sum |S_i| \log Q)\) 解法を紹介します。

クエリがオフラインで与えられているので、出現する文字列をソートした長さ \(Q\) のリスト \(L\) を構成できます。 すると、任意の文字列 \(s\) について、\(L\) の要素のうち \(s\) を接頭辞にもつものはある連続部分列をなします。 このような区間は二分探索で求めることができるので、クエリに高速を処理できます。

具体的には、次のようにすればよいです。 上記のリスト \(L\) に加えて、各要素が真偽値を取る長さ \(Q\) の列 \(P\) を管理します。 \(P[j]\) は \(L[j]\) が \(X\) のいずれかの要素をもつとき true、そうでないとき false をとり、クエリの処理とともに更新します。 また、\(Y\) に含まれる要素の \(L\) 内での位置の（多重）集合 \(M\) を管理し、これもクエリの処理とともに更新します。

最初、\(P\) の要素はすべて false で、\(M\) は空です。 \(i\) 番目のクエリは以下のように処理します。

• \(T_i=1\) のとき
  • \(L\) の要素のうち \(S_i\) を接頭辞にもつものが \(L[x..y]\) であるとします。
    • ただし、\(L[x..y]\) で \(L\) の要素のうち添字が \(x\) 以上 \(y\) 未満であるものがなす連続部分列を表します。
    • \(x, y\) は二分探索で求めることができます。
  • \(P[x..y]\) をすべて true とします。
  • \(M\) のうち \(x\) 以上 \(y\) 未満の要素を削除します。
• \(T_i=2\) のとき
  • \(L[x] = S_i\) なる \(x\) を一つとります。
    • 複数存在する場合は任意にとって構いません。
  • \(P[x]\) が false なら、\(x\) を \(M\) に挿入します。

\(M\) は通常の multiset を用いて実装できます。 \(P\) は「連続部分列内の全要素を true にする」「任意の要素を読み取る」という二種類の操作を高速に行えるデータ構造で保持する必要があります。 （遅延）セグメント木などを用いてもよいですが、累積和の考え方を使うと、長さ \(Q\) の BIT (Binary Indexed Tree) を使って以下のようにも実現でき、実装が簡便です。

• 最初、全要素を \(0\) とする。
• \(P[x..y]\) をすべて true としたいときは、BIT の \(x\) 番目の要素に \(1\) を足し、\(y\) 番目の要素に \(-1\) を足す。
• \(P[x]\) が false である必要十分条件は、BIT の \(x\) 番目までの要素（\(x\) 番目自身を含む）の和が \(0\) であることである。

実装例を以下に示します。

use std::collections::BTreeSet;

use ac_library::FenwickTree;
use itertools::Itertools;

fn main() {
    proconio::input! {
        q: usize,
        queries: [(u8, String); q],
    }
    let mut strs = queries.iter().map(|x| &x.1).collect_vec();
    strs.sort();

    let mut set = BTreeSet::new();
    let mut removed = FenwickTree::new(q, 0i32);
    for (i, (t, s)) in queries.iter().enumerate() {
        let pos = strs.binary_search(&s).unwrap();
        if *t == 1 {
            let x = strs.partition_point(|&st| st < s);
            let y = x + strs[x..].partition_point(|&st| st.starts_with(s));
            let poss = set.range((x, 0)..(y, 0)).copied().collect_vec();
            for pos in poss {
                set.remove(&pos);
            }
            removed.add(x, 1);
            removed.add(y, -1);
        } else {
            if removed.sum(..=pos) == 0 {
                set.insert((pos, i));
            }
        }
        println!("{}", set.len());
    }
}