ABC 350 G — Mediator

考察

現在グラフは常にforestなので、u,vが同じ木にあり共通隣接点wを持つなら、任意に根を付けたときwはparent[u]またはparent[v]のどちらかである。最終forestを先読みできれば候補は二つだが、queryが直前回答で暗号化されているためonlineで近似的に固定する必要がある。

採用する候補: queryをblock分割し、block前のforestだけ親・成分を再構築してblock内新辺を直接検査する

一blockごとのO(N)再構築と一queryごとのO(B)pending辺走査に分けられ、O(NQ/B+BQ)をB≈√NでO(Q√N)へ均衡できる。暗号化queryも到着順に復号して扱える。

棄却する候補: 全queryを復号して最終forestに根を付け、各質問でparent候補だけを見る

次queryの復号が過去のtype 2回答に依存するため、回答前に将来の辺を確定するoffline処理は循環してしまう。

棄却する候補: 辺追加のたびに現在forest全体のparentと成分を再計算する

一回O(N)、Q回でO(NQ)となり、N,Q≤10^5では実行できない。

block開始時forest G_0でu,vが同一成分なら、共通隣接点候補はparent[u],parent[v]だけである。別成分なのに現在は共通隣接点を持つなら、その二辺の少なくとも一方は現在blockで追加されたのでpending辺の走査で候補を拾える。

過去blockの全辺は親・component IDへO(N)で圧縮し、現在blockの高々B辺だけを未反映差分として残す。このbase+delta不変条件がonline性と平方根計算量を両立させる。

B件ごとに、それまでの全辺からforestをDFSしてparentとcomponentを再計算しpendingを空にする。辺追加は全体の隣接判定構造とpendingへ記録する。質問ではbase成分が同じなら二つのparent候補、異なるならuまたはvに接するpending辺の反対端を候補にし、現在辺集合で両隣接を確認して唯一のwまたは0を返す。

典型の発動条件

query平方分割

発動条件: 更新を完全反映した全体再構築は重いが、少数の未反映更新ならquery時に直接走査できる。

過去辺をO(N)の親・成分情報へ固め、block内のO(B)辺をdeltaとして残す。

根付きforestの距離2候補

発動条件: forest上で二頂点に共通して隣接する頂点を求めたい。

同一treeではparent[u]とparent[v]だけを候補にして実辺の存在を確認する。

問題固有の要素

暗号化はoffline化だけを封じており、過去を定期的に固定するblock処理は可能である。baseで別成分という情報が、答えを作る辺の少なくとも一方をdelta側へ限定する。

別の問題へ持ち帰る視点: online制約下では、全履歴を固定部分と小さい差分に分け、固定部分で候補を定数個へ絞るか、差分に証人が必ず現れることを示す。

正当性

既存成分内の共通隣接点は木の唯一の長さ2の経路上にあり、親二候補に含まれる。成分をまたぐなら、その経路に少なくとも一本の新辺があるため、差分の走査で拾える。最後に現在の辺で両隣接を確かめるので、候補の漏れも誤検出もない。

実装上の注意

  • a,b,cは必ず直前のtype 2回答を使って64 bitで復号し、その後にquery種別を判定する。pendingには現在blockで既に処理した辺だけを入れ、rootのparent=0を候補から除き、無向辺keyは端点順を正規化する。

復習の核

  • 小さいforestの隣接list全走査と比較し、u,vがbaseで同成分・別成分の両場合、共通点を作る一辺がpendingの場合、block先頭と末尾、答え0後の復号、rootが端点になる場合を確認する。

計算量と制約

時間

O(QN/B+QB)、森林の再構築O(N)、差分辺最大B。B≈√N。隣接hash検査は期待O(1)。

空間

O(N+B)。

制約との対応

公式制約の確認範囲: Time limit: 3 sec; Memory limit: 256 MiB; Constraints: All input values are integers.; 2 \le N \le 10^5; 1 \le Q \le 10^5; 1 \le u < v \le N; 0 \le a,b,c < 998244353

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: 平方根・閾値による軽重分類

主題
  • 平方根・閾値による軽重分類: 頻度・次数・更新回数を閾値でheavy/lightに分け、両側の計算量を均衡させる。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 平方根・閾値による軽重分類

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

      学習の位置

      体系上の位置: 平方根・閾値による軽重分類

      • 頻度・次数・更新回数を閾値でheavy/lightに分け、両側の計算量を均衡させる。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題