操作:辺を追加する
AtCoder
AtCoder475点
ABC-E
緑色diff
NoviSteps1Q
Union-Find
データ構造
クエリ処理問題
連結成分
取得:K番目に小さい値
マージテク
操作:辺を追加する
グラフ
Union-Findのマージ過程を表す木を考える
WaveletMatrix
Eulerツアー
Union-Find を上手に使おう！ 問題へのリンク 問題概要 初期状態では頂点数 、辺数 0 のグラフがある。頂点番号は である。次の 回のクエリに答えよ。 クエリタイプ 1：頂点 間に辺を張る クエリタイプ 2：頂点 を含む連結成分に含まれる頂点の番号にうち、 …
JOI
JOI予選・二次予選
JOI難易度5
AOJ
AtCoder
NoviSteps2Q
Dijkstra法
Floyd-Warshall法
クエリ処理問題
易しいクエリ処理問題
グラフ
クエリ(グラフ上)
【問題集】最短路問題
グラフや盤面が時間変化する最短路問題
最短路問題
操作:辺を追加する
取得:最大値・最小値
取得:最短路
実はクエリごとに毎回愚直に Dijkstra 法を回しても間に合う！ 問題へのリンク 問題概要 最初、辺数 0 本、頂点数 個のグラフが与えられる。頂点番号は である。このグラフに対して 回のクエリが投げられる。 クエリタイプ 0：2 頂点 が指定されるので、頂点…
AtCoder
AtCoder600点
ABC-F
Union-Find
連結成分
二部グラフ
二次元平面上のN点の問題
グラフ
可視化：二次元情報を二部グラフにして考える
制約条件:長方形の4頂点についての条件
青色diff
連結成分ごとに分解して考える
操作
操作後の結果の最適化問題
操作を好きな回数だけ行える
操作:辺を追加する
なんか既視感があった。それがどこから来たのか、いまだよくわからない。。。 問題へのリンク あと、今回のような二部グラフの作り方はあり本 P.205 の POJ 3041 Asteroids あたりもそんな感じ。こういうのを一度見ておくと、この二部グラフ作りは定石になる…
