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

525 stars 120 forks source link

[問題案] Persistent Queue #379

Closed noshi91 closed 4 years ago

noshi91 commented 4 years ago

問題名: Persistent Queue

想定アルゴリズム: 永続 Queue、永続平衡二分木など

問題概要

Q 個のクエリを処理

0 t x: クエリ t 直後の末尾に x を追加
1 t: クエリ t 直後の列の先頭要素を出力し、削除

入力

Q
query_0
query_1
:
query_{Q-1}

出力

制約

Q < 2*10^5 (調整)

検討事項

問題名 LIFO など、望ましい表現が存在するか
クエリ形式番号を振る方式で良いか
空の列をどうするか t=-1 にする、クエリの種類を追加するなど

yosupo06 commented 4 years ago

問題名はこれでいい気がします強いていうならpersistentの前に完全永続の完全に対応するものをいれる？

yosupo06 commented 4 years ago

クエリですが、-1でいいと思います(indexをずらして0にするか-1にするかの二択だと思うんですが、後者の方が良さそう)

noshi91 commented 4 years ago

とりあえず fully は付けずに作成してみます

yosupo06 commented 4 years ago

Fully Persistent Queueの使用例が全然見つからなかったんで、Persistent Queueで良さそう

Genius3435 commented 3 years ago

Could the statement for this problem be translated to English?

xindubawukong commented 2 years ago

hi @noshi91, how can we solve this problem? I can't understand what the solution code means. Do you have a tutorial for it? Thanks.

noshi91 commented 2 years ago

I apologize for forgetting to include references. The solution is based on a RealTimeQueue from Okasaki, C. (1999). Purely functional data structures. Cambridge University Press.