[問題案] Ordered Associative Array

[NyaanNyaan]

問題名: Ordered Associative Array 想定アルゴリズム: 平衡二分木, 動的セグ木(必要なところだけ作るセグ木)

問題概要

空の連想配列aが与えられます。以下で説明されるクエリを順にQ回処理してください。

0 k v : キーと値の組(k, v)をaに追加する。ただしキーがkである組が存在するときは、既存の組の値をvに書き換える。 1 k : キーがkである組をaから削除する。ただしキーがkである組が存在しないときは何もしない。 2 k : a[k]を出力する。(存在しない場合は-1を出力する。) 3 k : キーの値がk以下である組の個数を出力する。 4 i : i+1番目の組のキーと値(k, v)を出力する。(存在しない場合は-1を出力する。) 5 l r (sum_{(k,v) \in a, l <= k < r} v) を出力する。(存在しない場合は0を出力する。)

制約

• 1 <= Q <= 500,000
• 0 <= k < 10^9
• 0 <= v <= 10^9
• 0 <= i <= 500,000
• 0 <= l < r <= 10^9

検討事項

• Implicitでない平衡二分木のverify問題が前から欲しかったので立てました。

• ついでに動的セグ木のverify問もできると嬉しい人が多そうなので 0 <= k < 10^9 にして動的セグ木が十分高速に動く制約にしました。

• 題名は"Ordered Associative Array(順序付き連想配列)"が自然かと思ったのですが"Ordered Dictionary(順序付き辞書)"の方が圧倒的に使用例が多く悩ましい…

• 制約はQ = 10^6だとおそらくC++が2秒程度かかってしまうのでQ = 5 * 10^5にしました。

• 3のクエリが"i+1番目"となっているのはRange Kth Smallestでの議論を参考にしました。https://github.com/yosupo06/library-checker-problems/issues/310

[yosupo06]

• k番目が取得できるstd::mapと考えると、クエリ5はない方が自然だと思うのですが、どうでしょうか
• wikiにOrdered Dictionaryと書かれてあるので(https://en.wikipedia.org/wiki/Associative_array#Ordered_dictionary)、Ordered Dictionaryのほうが良さそうです

[NyaanNyaan]

• クエリ5がない方が自然というのに同意します。ただ、個人的には実用の観点からrange sumまでverifyしたいというのと、動的木のrange sumのためだけに別の問題を追加するよりは一緒にしてしまいたいという気持ちもあり入れてしまいました。(yosupoさんの方針に反するなら入れないつもりですが、出来れば入れたいです)
• Ordered Dictionary、了解です

[maspypy]

動的セグ木の提案が

https://github.com/yosupo06/library-checker-problems/issues/828

にもありますが、意図は同じだと思ってよいのでしょうか？こちらの方が解法の範囲が広がりますか？