ABC 401-500/ABC403E - Forbidden Prefix - 競技プログラミング用 知識集積所

---

問題

ABC403E

必要知識

B以下レベルの内容は省略

• 二分探索（未作成）

考え方

個数が少なければ、毎回Yの全内容それぞれについて、Xの全中身を見て接頭辞かチェックすればいい。
しかし、それでは毎回Xの文字数合計*Yの文字数合計だけ処理の必要があり、クエリ1と2が半々に来たら最後のクエリたった1つだけに10^10回以上の処理がかかる。
ということで、これをどうやって高速化するかが問題の中心となる。

まず最初に考えられるのは、Yの要素から接頭辞を持つ判定になったものを除外していくこと。
一度接頭辞がある判定になったYの要素は、二度と接頭辞がある判定状態にはならないのでYから削除してしまっても何も影響がない。
すると、XとYの組み合わせを毎回判定しなくても、追加分による影響を受ける分だけYから消して、Yに生き残っている個数を答えるだけで済む。

つまり、

• クエリ1が来た場合は、その文字列をXに追加しながらその文字列とYの中身の比較をする
• クエリ2が来た場合は、その文字列とXの中身の比較をして、結果次第でその文字列をYに追加する

で元より高速に答えが出せる。
しかしこれでも、クエリ1を10^5回連打されたあとクエリ2を10^5回連打されると、合計10^10回の比較が必要になってTLE。
もっと高速化する必要がある。

次に考えるのは、XやYの中身を常にソートしておいて、該当するものを二分探索すること。
もしそれがうまくいくなら、O(n*logn)くらいになりそうなので、間に合いそう。
（厳密に計算すると、O(文字数合計*logQ)になる）

しかし、これは新たな問題が発生する。
例えばXの中身が

{"abc","abcd","abce","abz"}

となっていた場合に、"abck"を検索すると接頭辞である"abc"とは全く違うところが示されてしまう。
今度はこの問題を解決しなければならない。

そこで、YだけでなくXの方も、同じXの中に接頭辞があるものは削除するようにする。
上の例の場合、"abcd"がXの中になくても、"abc"の判定でどうせひっかかるので、影響がないのである。
このように無駄なものを削除すると、"abc"と"abck"の間に別のものが残っている可能性がないため、二分探索がうまくいくようになる。

まとめると、

• クエリ1が来た場合は、
  • その文字列を接頭辞にもつXの中身を二分探索を使って全て削除する
  • その文字列とXの中身を二分探索で比較をして、結果次第でその文字列をXに追加する
  • その文字列を接頭辞にもつYの中身を二分探索を使って全て削除する
• クエリ2が来た場合は、
  • その文字列とXの中身を二分探索で比較をして、結果次第でその文字列をYに追加する

をすればよい。

解答例

解答例

注意点

• setの二分探索は.lower_bound()などを使う。

std::lower_boundは、ランダムアクセスイテレータの場合（vectorやdequeなど）に高速で探索する関数であり、setなどではむしろ低速。
setの中に用意されている.lower_bound()の方を使うこと。

別解

• Trie木（未作成）を使う。

公式解説参照。