Ranks change; identities do not
Update ranked sets and optionally preserve duplicate occurrences with IDs.
A rank belongs to the current state
In {5, 12, 20}, 12 has rank 1. Insert 8 and its rank becomes 2. If a command later erases 5, the ranks shift again. Store an actual key or ID to remember an item; a saved rank is not a stable identity.
A dynamic distinct-key command processor can insert(x), erase(x), order_of_key(x), and guarded find_by_order(k). Queries do not create keys. With q commands, a safe bound including input work is O(q(1 + log(q + 1))); storage follows the maximum live set.
Optional extension: duplicate values need distinct full keys
Represent each occurrence as (value, unique_id) in a PBDS tree with std::less<pair<int,int>>. Pair order compares value first, then ID. Equal values remain adjacent, but each occurrence is a different full key.
If IDs are 0 through n − 1, order_of_key({x, -1}) counts occurrences strictly below x, while order_of_key({x, n}) counts those at most x. The sentinels are justified by the ID range. Do not recycle an ID while its old pair remains stored; do not use x + 1 when a pair boundary avoids possible overflow.
// Complete GNU PBDS extension program in C++23 mode. No input.
#include <functional>
#include <iostream>
#include <utility>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using Item = std::pair<int, int>;
using OrderedBag = __gnu_pbds::tree<
Item, __gnu_pbds::null_type, std::less<Item>,
__gnu_pbds::rb_tree_tag,
__gnu_pbds::tree_order_statistics_node_update>;
int main() {
OrderedBag values;
values.insert({5, 0});
values.insert({2, 1});
values.insert({5, 2});
values.insert({8, 3});
std::cout << values.order_of_key({5, -1}) << '\n';
std::cout << values.order_of_key({5, 4}) << '\n';
auto ranked = values.find_by_order(2);
if (ranked != values.end()) std::cout << ranked->first << '\n';
auto one = values.lower_bound({5, -1});
if (one != values.end() && one->first == 5) {
Item key = *one;
values.erase(key);
}
std::cout << values.size() << '\n';
}Erase the occurrence you actually found
To remove one 5, lower_bound({5, -1}) locates the first possible 5. Check both end() and the value field, copy the full pair key, then erase that key. A bound may point to the next larger value when 5 is absent.
The program prints 1, 3, 5, 3: one value is below 5, three are at most 5, rank 2 has value 5, and one occurrence is removed. Strict ordering remains valid throughout.
Pairs (4,0), (4,1), (9,2) are stored. Which claim is true?
Turn the idea into code
A ranked distinct set starts as {5, 12, 20}. Insert 8, erase 5, then ask for rank 1 and the number of keys below 12. Explain why an earlier saved rank may be misleading.
Give me a hint
Rebuild the sorted state after every update.
Show the explained solution
The states are {5, 8, 12, 20}, then {8, 12, 20}. Rank 1 is now 12, and one key is below 12. An earlier rank can identify a different item after updates; retain the key when identity matters.
Your notes
Mark complete when you can explain it yourself.