[問題案] Incremental Graph Component Affine Vertex Get Component Sum

[suisen-cp]

https://github.com/yosupo06/library-checker-problems/issues/783 + 遅延評価

Problem

$N$ 頂点の辺のないグラフ $G$ がある。はじめ、頂点 $i$ には整数 $a _ i$ が書かれている。以下の形式のクエリを $Q$ 個処理。

• 0 u v: $G$ に無向辺 $\lbrace u, v\rbrace$ を追加
• 1 v x: $a _ v \leftarrow x$ と更新
• 2 v b c: $G$ において $v$ と連結な全ての頂点 $u$ に対して $a _ u \leftarrow b a _ u + c$ と更新
• 3 v: $a _ v$ を $998244353$ で割った余りを出力
• 4 v: $G$ において $v$ と連結な全ての頂点 $u$ に亘る $a _ u$ の和を $998244353$ で割った余りを出力

Constraint

• $1\leq N \leq 5\times 10 ^ 5$
• $1\leq Q \leq 5\times 10 ^ 5$
• $0 \leq a _ i \lt 998244353$
• $0 \leq v \lt N$
• $0 \leq x \lt 998244353$
• $1 \leq b \lt 998244353$
• $0 \leq c \lt 998244353$

Reference

• https://atcoder.jp/contests/cf17-tournament-round3-open/editorial/1946

Notes / Discussion

• $b _ i = 0$ があり得る場合 (作用が非可逆であり得る場合) に上記の方法で高速に解けるかは分かりません。
  • 各クエリが区間作用とか区間取得になるように頂点を並び替えれば遅延セグ木で処理できて、この解法なら $b _ i \neq 0$ は要らなさそう

[maspypy]

問題タイトル通り「Component Affine Component Sum」ならめちゃくちゃ簡単で。

非自明なのは 3 かな。クエリ 0, 2, 3 だけとかの方が意図が分かりやすい感じもしますが、好みかもしれません。

「1」 は入れるなら、 「 $a_v$ に $x$ を代入」でよい気がしています。（遅延セグ木とかでも、1点に対する apply を専用実装している人はあまりいない気がします）

[suisen-cp]

問題タイトル通り「Component Affine Component Sum」ならめちゃくちゃ簡単で。

非自明なのは 3 かな。クエリ 0, 2, 3 だけとかの方が意図が分かりやすい感じもしますが、好みかもしれません。

確かに Component Sum がおまけなので問題名は Incremental Graph Component Affine Vertex Get Component Sum とか Incremental Graph Component Affine Vertex Get の方が適切でしょうか？

「1」 は入れるなら、 「 $a_v$ に $x$ を代入」でよい気がしています。（遅延セグ木とかでも、1点に対する apply を専用実装している人はあまりいない気がします）

同意です

[maspypy]

Incremental Graph Component Affine Vertex Get Component Sum これでいいかな。

[maspypy]

作業者募集。