[問題案] Persistent Meldable Heap

Open hotman78 opened this issue 4 years ago • 3 comments

(任意) 問題ID: persistent_meldable_heap 問題名: Persistent Meldable Heap

(任意) 想定アルゴリズム: Persistent Leftist Heap (任意) 参考資料: https://scrapbox.io/data-structures/Leftist_Heap

問題概要

N個の集合が与えられるので、Q個のクエリを処理 0 t x:集合tに非負整数xを追加 1 t :集合tの最小値を出力し削除、なければ-1を出力し集合tに変更は加えない。 2 s t:集合sに集合tの要素を全て追加、集合tは変更しない

N Q query_0 query_1 : query_{Q-1}

N,Q < 5*10^5

Jun 04 '20 14:06 hotman78

クエリ2を行うと要素数が2倍に増えるはずで、なので2^{500000}ぐらいのサイズのheapが出来て、するとO(log 要素数) = 500000ぐらいになって、計算量が破滅する気がします

Jun 04 '20 19:06 yosupo06

確かにそうですね... あまりいい方法が思い浮かんでません要素数が一定値を超えないことを保証するとかですかね...

Jun 05 '20 01:06 hotman78

persistent meldable heapそのものではなくて、それを使う問題でベリファイする(k-th shortest walkとかそうだった気がします)
要素数が適当な値(10^18とか？)を超えないことを保証する
meldable heapにする

ぐらいですかね

Jun 05 '20 10:06 yosupo06