[問題案] Range Unionfind

[SSRS-cp]

問題名: Range Unionfind (?)

問題

N 頂点の無向グラフがある。最初辺はない。Q クエリ処理

1 L R D: (L,R), (L+1,R+1), ..., (L+D-1,R+D-1) にそれぞれ無向辺を追加。多重辺ができることもある。 2 U V: 頂点 U, V が連結かどうか答える (Yes/No)

解法

各連結成分に代表の頂点を定める。v の連結成分の代表を p[v] とする。 クエリ 1 で p[L,L+D) と p[R,R+D) が列として一致しない間、一致しない箇所を 1 つ見つけ、その 2 頂点を unite する。UnionFind で各連結成分の頂点の集合を取得できるようにし、少ない方について p をすべて更新する。セグ木にロリハで列の一致を判定する。

$O((N+Q) \log^2 N)

制約

$N, Q \leq 200000$ くらい

[hos-lyric]

2 冪ごとに union find を持って deterministic $O((N \log(N) + Q) \alpha(N))$ くらいになると思います 参考：https://img.atcoder.jp/yahoo-procon2018-final-open/editorial.pdf の D

(https://judge.yosupo.jp/problem/persistent_unionfind にも言えるんですが) 0/1 だとあんまり強くないので情報量が多いものを出力させたい気持ちもあります 頂点に重みをつけて (連結成分内の積) の総和 mod 998244353 とか

「L, L+1, ..., R-1 を全部まとめてください」も range union find っぽいので名前は要検討かもしれません (対案はないです，すみません)

[yosupo06]

https://yosupo.hatenablog.com/entry/2019/11/12/001535 ? たしか線形で解けるって話もあった気がします

[yosupo06]

ああ連結判定が動的に来るんですね　すいません

[hos-lyric]

https://codeforces.com/contest/1801/problem/E 文脈を貼っておくとこの問題です (木のパスで同じことをする．動的に union find の状態を出力する) ただし木なので逆向きも要ります ライブラリ的にも少し変わるので逆向きに繋ぐクエリがあってもいいかもしれないし，なくてもいいかもしれないです (結局交差が定数種類なら等差数列についてできるという話ではあります)

[SSRS-cp]

逆向きがある場合どのように変わることを想定していますか

[hos-lyric]

考え直した結果，方向が k 種類あったら union find の頂点数が k N 要るというだけのことでした (「逆向きだけ」でも 2 N 頂点要るのでちょっと違う気がしてしまっていました)

[NachiaVivias]

名前ですが、 Range Parallel Unionfind （あるいは、総和クエリの場合の内容から Range Parallel Unite Get Sum ）はどうですか？

[NachiaVivias]

出力クエリについて、以下のような設定にする提案が上がっています。（ discord にて、 熨斗袋より）（以下、原文よりも具体的にしています）

（出力クエリを省く。）

各クエリを処理した後、次で定義される値 $W$ を出力してください。

• $u$ と $v$ が連結ならば、 $f(u,v)=1$ そうでなければ $f(u,v)=0$ とする。
• $W= \left( \sum {0 \leq u \lt v \leq N-1} f(u,v) X u X _ v \right) \bmod 998244353$

個人的には、バグ取りの効率が非常に高まるように感じており、ぜひそうしたい気持ちなのでここで改めて提案しました。