-
-
Notifications
You must be signed in to change notification settings - Fork 112
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
[問題案] Range Unionfind #934
Comments
2 冪ごとに union find を持って deterministic (https://judge.yosupo.jp/problem/persistent_unionfind にも言えるんですが) 「L, L+1, ..., R-1 を全部まとめてください」も range union find っぽいので名前は要検討かもしれません |
https://yosupo.hatenablog.com/entry/2019/11/12/001535 ? たしか線形で解けるって話もあった気がします |
ああ連結判定が動的に来るんですね すいません |
https://codeforces.com/contest/1801/problem/E |
逆向きがある場合どのように変わることを想定していますか |
考え直した結果,方向が k 種類あったら union find の頂点数が k N 要るというだけのことでした (「逆向きだけ」でも 2 N 頂点要るのでちょっと違う気がしてしまっていました) |
名前ですが、 Range Parallel Unionfind (あるいは、総和クエリの場合の内容から Range Parallel Unite Get Sum )はどうですか? |
出力クエリについて、以下のような設定にする提案が上がっています。( discord にて、 熨斗袋より)(以下、原文よりも具体的にしています)
個人的には、バグ取りの効率が非常に高まるように感じており、ぜひそうしたい気持ちなのでここで改めて提案しました。 |
問題名: 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)
制約
The text was updated successfully, but these errors were encountered: