Trie等の高度なデータ構造を使わず、STLのstd::multisetのみを用いる \(O(\sum |S_i| \log(Q))\) 解法です。

以下のような文字列の集合 \(X'\) と多重集合 \(Y'\) をstd::set/std::multisetで陽に管理することを考えます(multisetは文字列の大小を辞書順で比較します)

\(X'\): \(X\) のうち”冗長でない”要素の集合、すなわち \(X\) の要素 \(s\) であって、その \(s\) 以外の接頭辞が \(X\) に含まれないものの集合
\(Y'\): \(Y\) のうちクエリで数えられるべき要素の集合、すなわち\(Y\) の要素 \(s\) であって、その接頭辞が \(X\) に含まれないものの集合

クエリの答えは \(|Y'|\) です。 クエリ時の \(X', Y'\) の更新は以下の通りです

• \(X\) に \(S_i\) を追加する場合
  
  • \(X'\) の更新:
    1.1. \(S_i\) の接頭辞が \(X'\) に既にあるなら何もしない
    1.2. \(S_i\) を接頭辞に持つ \(X'\) の要素をすべて削除
    1.3. \(X'\) に \(S_i\) を追加
    
  • \(Y'\) の更新:
    1.4. \(S_i\) を接頭辞に持つ \(Y'\) の要素をすべて削除
• \(Y\) に \(S_i\) を追加する場合
  \(X'\) は変わらず
  2.1. \(S_i\) の接頭辞が \(X'\) にないなら \(Y'\) に\(S_i\) を追加

ここで以下の2種類の操作が必要になると思います
A. 与えられた文字列 \(s\) の接頭辞が \(X'\) にあるか判定(1.1, 2.1)
B. 与えられた文字列 \(s\) を接頭辞に持つ \(X'\) または \(Y'\) の要素をすべて削除(1.2, 1.4)

これは以下のように行えます
A:
\(s\) の接頭辞は存在するならprev(\(X'\).upper_bound(\(s\)))の位置にあるので、そこを見ればよいです
証明: そうならないのは、\(s\) の接頭辞 \(s'\) と、\(s\) の接頭辞ではない \(t\) が共に \(X'\) 内に存在して \(s' < t \le s\) となる場合だが、よく考えると \(t\) は \(s'\) を接頭辞に持っていないとおかしいので、\(X'\) の定義に反する(\(t\) が冗長)

B:
\(s\) を接頭辞に持つ \(S\) の要素は、存在するならば \(S\).lower_bound(\(s\))から開始する連続する区間にあります -> 実際に接頭辞になっているかを判定して1つずつmultisetから消していけばよいです
計算量:
接頭辞の判定は2つの文字列の長さのminでできる。
実際に接頭辞だったため消した分については、消された方の長さの時間と考えて、消された要素が追加されたときのクエリの計算量の一部と考えて償却解析できる。
接頭辞でなかったような場合は最後の \(1\) 回しか起こらないので、\(|s|\) の時間と考えて今回のクエリの計算量にカウントすれば \(O(\sum |S_i|)\) に吸収される。

実装例:

#include <bits/stdc++.h>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

bool is_prefix(const std::string &s, const std::string &t) {
	if (s.size() > t.size()) return false;
	return s == t.substr(0, s.size());
}

int main() {
	int q = ri();
	
	std::multiset<std::string> x;
	std::multiset<std::string> y;
	
	for (int i = 0; i < q; i++) {
		int t = ri();
		std::string s;
		std::cin >> s;
		if (t == 1) {
			auto itr = x.upper_bound(s);
			if (itr != x.begin() && is_prefix(*std::prev(itr), s)) {}
			else {
				while (itr != x.end() && is_prefix(s, *itr)) itr = x.erase(itr);
				itr = y.lower_bound(s);
				while (itr != y.end() && is_prefix(s, *itr)) itr = y.erase(itr);
				x.insert(s);
			}
		} else {
			auto itr = x.upper_bound(s);
			if (itr != x.begin() && is_prefix(*std::prev(itr), s)) {}
			else {
				y.insert(s);
			}
		}
		printf("%d\n", (int) y.size());
	}
	
	return 0;
}