D - Range Set Insertion Query Editorial by seekworser Editorial for printing


やや発展的な解法です。

セグメントツリーの要領で長さが2べきの区間ごとにHashsetを管理することにします。各クエリを(セグメント木の要領で)高々 log 個の区間に分割し、該当の区間に対応するHashsetに値を配置します。 (サンプル1では例えば以下の画像のようなイメージです)

その後、根のノードからHashsetを管理しながらDFSを行って、葉のノードでHashsetのサイズを記録することで答えを求めることができます。(値ごとにHashsetに追加されたノードを保持しておいて、RollbackすることでHashsetを適切に更新することができます。詳しくは実装例を参照してください。)

実装例(Nim)

posted:
last update: