Hello people of Codeforces :)
I was solving a problem that had two types of operations: 1 — Insert element X the sequence 2- What is the kth largest element of the sequence. How to solve this type of problem?
The sequence may have 10 ^ 5 elements, and may have 10 ^ 5 queries.
Tks. :D
Treap data structure will be extremely useful ;)
You can do these types of operations quite easily with any balanced binary search tree. I prefer a Treap because the tree rotations that occur after insertion/deletion are very simple. Others might be a splay tree, red-black tree, AVL, etc. You can keep track of the number of elements stored in the subtree of each node in your tree, then it becomes easy to count the number of elements smaller than X. You can insert, delete and count the kth largest in O(log(N)) time.
You can take the sequence and the insert queries first. Sort the elements according to their values (including insert queries) and give them sorted indices in the final sequence. Set all elements position of the initial sequence to 1 and insert queries to 0. For each insert query you can update the element's position to 1. To get the Kth element you just need to find the smallest index where the cumulative sum is K from the first position. You can easily manage this update and find query with a segment tree. Complexity of per insert and find query of this technique is O(log(N)).
Hello! You can learn about Indexed Set in C++ (it is policy-based data structure). Antti Laaksonen (pllk) also wrote about that in his book (here you can download and find about Indexed Set in page 44).
Indexed Set can find position of x and x'th element in set in O(logn) but constant of complexity is a little big. Here I wrote program with Indexed Set for finding k'th maximum in array:
UPD: I found problem like that with delete update, original solution is by treap, but my code with Indexed Set got AC 135ms. https://www.e-olymp.com/en/problems/687
Solution: https://pastebin.com/10iu04L9
TooNewbie, Is there any similar policy based DS to find kth smallest element in which there can be duplicate elements?. Indexed set gives wrong answer on duplicate elements. Is there indexed multiset ?
You can do it with the same DS. Simply when inserting, maintain a pair<value, idx>, where idx is the index of the element you are inserting. If you didn't understand what I mean you can imagine that you will have indexed_set<pair<int, int> > S and a map<int, int> M keeping the number of elements with a given value.
Then the insert will be something like:
S.insert({x, M[x]++});
And the delete will be something like:
S.erase({x, --M[x]});
UPD: To find K-th smallest element, you will have to do S.find_by_order(K).first and to find number of elements with value less than K, you will do S.order_of_key({K, -1}).
You can use a pair in indexed set. For example, if x has 3 duplicates in set, let them be {x,1}, {x,2}, {x,3}. Note that while comparing pairs priority of the first element of pair is more than second.
EDIT: Snipped by Radoslav :P
When defining the indexed set, you can use less_equal as comparer instead of less. This makes the set work as a multiset. Both inserting and kth element work, but remove() isn't guaranteed to work correctly in this case.
This topic is related to a problem in an on going contest, so can you please discuss it after the end of "Week of Code 38" on HackerRank.
You can solve this problem with O(log(n)²) per query. Just make a binary search over X and use a BIT (Segtree, whatever) to determine how many elements are bigger than X, with this you can determine if you have to go left or right.
You can do better using just a SegTree.
You can do binsearch in segtree in O(log(MAX)).
You can do in O(log n) using a binary search tree, a BIT or a segtree... all of them support binary searching in O(log n)
I know that. I'm the author of the problem, so I just wanted to mention one of the simplest ways to solve it.
No hard data structures are needed if K is constant (see replies). Please write more detailed constraints.
i thought K is not constant
K is no constant. For each query you have a new value of K.
I understand why they suggested balanced search trees. I think BIT is easiest and fastest if range of X is enough small. (Also thank you RapperGuy.)
Could you give the link to the problem? Thanks!
I wrote the problem in Portuguese without translation, if you want I can share the link
There's a harder version here: http://www.spoj.com/problems/ORDERSET
Here with delete update: https://www.e-olymp.com/en/problems/687