yosupo06 / library-checker-problems

The problem data (Test case generator, judge's solution, task, ...) of Library Checker

https://judge.yosupo.jp/

Apache License 2.0

522 stars 118 forks source link

Open hotman78 opened 4 years ago

hotman78 commented 4 years ago

(任意) 問題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 query1 : query{Q-1}

N,Q < 5*10^5

yosupo06 commented 4 years ago

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

hotman78 commented 4 years ago

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

yosupo06 commented 4 years ago

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

ぐらいですかね