[問題案] Incremental Dynamic Graph Vertex Add Component Sum

Open SSRS-cp opened this issue 2 years ago • 4 comments

問題ID: ? 問題名: Incremental Dynamic Graph Vertex Add Component Sum

想定アルゴリズム: UnionFind に可換モノイドを載せるやつ

問題概要

N 頂点 0 辺の無向グラフがある。各頂点に値 a_i が書かれている。Q クエリ処理 0 u v: 辺 (u,v) を追加 1 v x: a_v←a_v+x 2 v: 頂点 v と連結な頂点に関する a の和を出力

N Q
a_0 a_1 ... a_{N-1}
Query_0
Query_1
...
Query_{Q-1}

2 v の形式のクエリごとに答えを 1 行出力

1 <= N <= 500000 1 <= Q <= 500000 0 <= a_i, x <= 10^9

関連: #33 連結成分の大きさのクエリも Verify 可能

上位互換: #347

(追記) 作業はできないです

Jun 23 '22 22:06 SSRS-cp

良さそうです　名前は Incremental Dynamic Graph Component Sumがいい気がします　頂点の値加算も入れてもいいかも

Jun 27 '22 13:06 yosupo06

そういえば頂点加算もできましたね、入れて Incremental Dynamic Graph Vertex Add Component Sum にします

Jun 28 '22 08:06 SSRS-cp

作業者募集

Mar 26 '23 17:03 maspypy

Incremental Dynamic Graph はくどい気がするので、問題追加するときに Incremental Graph にしてもよいでしょうか？

Apr 06 '23 14:04 NachiaVivias