D - Range Set Insertion Query Editorial
by
seekworser
やや発展的な解法です。
セグメントツリーの要領で長さが2べきの区間ごとにHashsetを管理することにします。各クエリを(セグメント木の要領で)高々 log 個の区間に分割し、該当の区間に対応するHashsetに値を配置します。
(サンプル1では例えば以下の画像のようなイメージです)
その後、根のノードからHashsetを管理しながらDFSを行って、葉のノードでHashsetのサイズを記録することで答えを求めることができます。(値ごとにHashsetに追加されたノードを保持しておいて、RollbackすることでHashsetを適切に更新することができます。詳しくは実装例を参照してください。)
