ABC 219 G — Propagation

考察

一回の query は中心 x の現在値を全近傍へ上書きするため、次数の大きい頂点が何度も選ばれると隣接リスト走査の総量が大きくなる。一方、次数 B 以上の頂点数は次数和から高々 2M/B 個である。

更新は加算ではなく代入なので、各頂点の正しい値は自分へ届いた更新のうち時刻が最大の一つだけで決まる。高次数頂点からの配布は、その頂点に値と時刻の看板を残して遅延できる。

採用する候補: 次数 B 未満の query は全近傍へ即時反映し、次数 B 以上なら看板だけを更新する。頂点の値が必要な時に隣接する高次数頂点の看板から最新時刻を解決する。

軽頂点の隣接走査を B 未満に抑え、遅延更新の確認先も高次数頂点数以下に抑えることで、疎グラフの次数和を利用できる。

棄却する候補: 全 query で x の隣接頂点を列挙して値を書き換える。

星型などで中心が繰り返し指定されると、一回 Θ(N) の更新が Q 回発生する。

頂点 v を参照する直前に、v の明示値の時刻と v に隣接する全 heavy 頂点の看板時刻を比較すれば、未配布の代入を含む現在値を復元できる。

閾値 B を √M 程度に置き、各頂点について隣接 heavy 頂点を前計算する。query x の先頭で x を最新化し、x が light なら全近傍の値・時刻を更新、heavy なら x の看板へ値・時刻を保存する。全 query 後も各頂点を同じ方法で最新化して出力する。

典型の発動条件

次数平方分割

発動条件: グラフ query の一回の費用が中心頂点の次数に比例し、辺数の総和だけが小さいとき。

低次数は push、高次数は lazy にし、閾値 B と heavy 頂点数 M/B の釣り合いを取る。

timestamp による遅延代入

発動条件: 複数の上書き更新が競合し、最も新しい更新だけを採用すればよいとき。

値と query index を組で保存し、参照時に最大 timestamp の候補を選ぶ。

問題固有の要素

heavy 頂点の更新先を列挙しない代わりに、各受け手から「隣接 heavy の看板」を見に行く向きへ反転できる。

別の問題へ持ち帰る視点: 高次数からの broadcast が重いとき、更新を発信者に置き、必要時に受信者が少数の重い発信者だけを pull できないか考える。

正当性

各更新は、即時反映した値か発信元の看板のどちらかに記録される。受け手がその両方から最新時刻を選ぶため、必要な代入を落とさず、古い代入で上書きすることもない。発信前にもこの処理を行うので、配布する値自体が常に正しい。

実装上の注意

  • query x 自身の現在値を必ず解決してから配布する。heavy の看板は x 自身ではなく近傍への更新を表し、最後の出力前にも全頂点を再解決する。

復習の核

  • heavy 中心が看板を立てた直後に、その隣の light 頂点が発信者になる例を追い、「発信前の resolve」が必要な箇所を確認する。

計算量と制約

時間

O(N+M+Q(B+M/B))。B=max(1,⌈√M⌉)、heavyは高々2M/B個。最後に全頂点を最新化する時も、全heavy隣接リストの総長は2M以下なのでO(N+M)で済む。M=0ではB=1として零除算を避ける。

空間

O(N+M)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 2 \times 10^5; 0 \leq M \leq \min(2 \times 10^5, N(N-1)/2); 1 \leq Q \leq 2 \times 10^5; 1 \leq u_i, v_i \leq N; 1 \leq x_i \leq N; The given graph is simple. In other words, it has no self-loops and no multi-edges.; All values in input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

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

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

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

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

      学習の位置

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

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

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題