ABC 279 F — BOX

考察

box移動は多数のballを一括して別boxへ移すため、ballごとのbox番号更新では同じ巨大集合を何度も走査し得る。操作1はball集合の併合であり、各boxが現在どのDSU componentを持つか、各componentがどのboxにあるかを対応付ければよい。DSU leaderはunion by sizeで変わり得るため、union後に返された新leaderへowner boxを設定し直す。空boxにはcomponentがないというsentinelを持てば、空→非空移動・非空同士union・新ball追加を同じ対応で処理できる。

採用する候補: ballをDSU要素にし、box→component leaderとleader→boxの双方向mapを更新する。

集合併合と新ball追加をamortizedに処理し、queryはballのleaderからboxを即座に得られる。

棄却する候補: 各boxにball listを持ち、type1でYの全ballの所属boxをXへ書き換える。

大集合を箱間で繰り返し移す入力では総更新数が二次になり得る。

最大N+Q ballのDSUを用意し、rootOfBox[x]とboxOfRoot[r]を持つ。move Y→Xは空caseを分けてcomponentをunionしYを空にする。addはsingleton ballをX componentへunionし、query ball bはboxOfRoot[find(b)]を返す。

典型の発動条件

DSU componentへのmetadata付与

発動条件: 集合の併合と、要素が属する集合の外部属性queryが混在するとき。

leaderにbox番号を紐付け、leader変更後にmetadataを新rootへ移す。

containerとcomponentの間接参照

発動条件: 多数要素のcontainer移動を個別更新したくないとき。

containerは集合代表だけ、query要素はfind経由でcontainerへ到達する。

問題固有の要素

boxがball集合を所有するのではなく、DSU componentとboxの対応だけを動かすと、10^100個という表現上のball上限も実際の追加数N+Qへ縮む。

別の問題へ持ち帰る視点: bulk moveでは要素属性を書き換えず、集合objectへのpointer/代表とownerの対応を付け替える。

正当性

非空箱に球成分、成分代表に所有箱を対応させる。移動は成分併合または移管、追加は singleton 併合なのでこの不変条件を保つ。union後の新代表に所有箱を書き直せば代表変更にも対応し、find(ball) の所有箱が正しい。

実装上の注意

  • Yが空なら何もせず、Xが空ならunionせずcomponent pointerだけ移してYを空にする。
  • union後は旧leaderを使わず新leaderをrootOfBox[X]へ保存し、boxOfRoot[newLeader]=Xを必ず更新する。

復習の核

  • 大集合をbox1→2→3と移す例で、ball側は一度も更新せずowner[root]だけが変わることを追跡する。

計算量と制約

時間

初期球 N、操作 Q。O((N+Q)α(N+Q))。

空間

球 DSU と箱対応で O(N+Q)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: All values in the input are integers.; 2 \le N \le 3 \times 10^5; 1 \le Q \le 3 \times 10^5; For each type-1 operation, 1 \le X,Y \le N and X \neq Y.; For each type-2 operation, 1 \le X \le N.; For each type-3 operation, ball X is contained in some box at that point.; There is at least one type-3 operation.

出典

分類・前提・執筆情報

掲載状態: 収録済み

BOX の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: DSUによる連結成分管理・縮約

主題
  • DSUによる連結成分管理・縮約: 成分へmetadataまたはmerge履歴を集約し、成分を一頂点に縮約した隣接関係、または併合後の代表情報を構成できる。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: DSUによる連結成分管理・縮約

      執筆: abc-explanation-author1.1.1 / revision 2

      学習の位置

      体系上の位置: DSUによる連結成分管理・縮約

      • 成分へmetadataまたはmerge履歴を集約し、成分を一頂点に縮約した隣接関係、または併合後の代表情報を構成できる。

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題