\(X\) の要素をprefixに持つ文字列は \(Y\) から取り除くことにします。（表現の簡略化のためであり、本質的ではありません）

文字列 \(S\) に対応する trie の各 node に次の 2 つの要素を持たせます。

• \(\mathrm{flag}\) ： \(S\) が \(X\) に含まれるかどうかを表す真偽値
• \(\mathrm{cnt}\) ： \(S\) を prefix に持つ \(Y\) の要素の個数

「文字列 \(S\) に対応する node が持つ \(\mathrm{cnt}\) の値」を \(S_{\mathrm{cnt}}\) と略記することにします。

この trie の更新は以下のようにできます。

• 文字列 \(S\) を \(X\) に追加するとき

  • trie をたどり、\(X\) の要素を prefix に持つか判定します。
    • 持つなら何も更新する必要はありません。
    • 持たないならば \(S_\mathrm{flag}\) を更新し、\(S\) までのパス上の node の \(\mathrm{cnt}\) から \(S_{\mathrm{cnt}}\) を引きます。
      これは \(O(|S|)\) でできます。（これ以降 \(S\) の子孫の node にアクセスすることはないため、それらの node の情報をここで更新する必要はありません）

• 文字列 \(S\) を \(Y\) に追加するとき

  • trie をたどり、\(X\) の要素を prefix に持つか判定します。
    • 持つなら何も更新する必要はありません。
    • 持たないならば、\(S\) までのパス上の node の \(\mathrm{cnt}\) に \(1\) を加えます。
      これは \(O(|S|)\) でできます。

• クエリに答えるとき

  • \((空文字列)_{\mathrm{cnt}}\) が求める値であり、これは \(O(1)\) で取得できます。

以上より、\(O(Q+\sum|S_i|)\) で解けました。