取得:K番目に小さい値
AtCoder
AtCoder475点
ABC-E
緑色diff
NoviSteps1Q
Union-Find
データ構造
クエリ処理問題
連結成分
取得:K番目に小さい値
マージテク
操作:辺を追加する
グラフ
Union-Findのマージ過程を表す木を考える
WaveletMatrix
Eulerツアー
Union-Find を上手に使おう！ 問題へのリンク 問題概要 初期状態では頂点数 、辺数 0 のグラフがある。頂点番号は である。次の 回のクエリに答えよ。 クエリタイプ 1：頂点 間に辺を張る クエリタイプ 2：頂点 を含む連結成分に含まれる頂点の番号にうち、 …
数列の区間について、 番目に小さい値を求めていく。Wavelet Matrix で処理できる典型クエリ！ 問題へのリンク 問題概要 サイズ の数列 が与えられる。次の 個のクエリに答えよ。 区間 において 番目 (0-indexed) に小さい数を答えよ 制約 考えたこと Wavele…
AtCoder
AtCoder500点
ABC-E
水色diff
K番目を求める
priority_queue
データ構造テク：全体に反映させる値を別にもつ(遅延評価)
BinaryTrie
BIT
BIT上二分探索
データ構造
クエリ処理問題
WaveletMatrix
setの上手な使い方
座標圧縮
データ構造テク：差分更新
セグメント木
数列
区間
各kに対して
クエリ先読み
典型要素を詰め合わせた教育的問題
削除可能priority_queue
操作:挿入
操作:削除
取得:K番目に小さい値
セグメント木上の二分探索
よくあるデータ構造問題！！ めっちゃ色んな解法がある！ 問題へのリンク 問題概要 長さ の整数列 と整数 が与えられる (0-indexed で表している)。 各 に対して、次の問題に答えてください。 個の整数 を小さい順に並び替えたときの先頭 個の総和を求めよ。…
